#include<bits/stdc++.h>
using namespace std;
int main(){
	int a0,a1,p,q,k;
	while(cin >> a0 >> a1 >> p >> q >> k){
		int a[10005];
		a[0] = a0;
		a[1] = a1;
		for(int i=2;i<=k;i++)
			a[i]=(p*a[i-1] + q*a[i-2])%10000; //递推每一步计算后立即取模，避免溢出
		cout << a[k]%10000 << endl;	
	}
	return 0;
}