清华大学机试 递推数列 Eays *注意取模公式，现场打表快于递归，这是第一次的实践

#include<iostream>
#include<vector>
using namespace std;

const int mod = 10000;
int a, b, p, q, k;

int num[mod];

void init() {
	num[0] = a;
	num[1] = b;
	for (int i = 2; i <= k; i++) {
		num[i] = (num[i - 1] * p) % mod + (q*num[i - 2]) % mod;
		num[i] %= mod;
	}
}

//int charge(int k) {
//	if (k==2) {
//		return ((p*b) % mod + (q*a) % mod) % mod;
//	}
//	else if (k == 1) {
//		return b;
//	}
//	else if (k == 0) {
//		return a;
//	}
//	else {
//		return ((p*charge(k - 1)) % mod + (q*charge(k - 2)) % mod) % mod;
//	}
//}

int main() {

	while (cin >> a >> b >> p >> q >> k) {
		init();
		cout << num[k] << endl;
	}
}