#include<iostream>
using namespace std;

int main() {
	int a0,a1,a2,p,q,k;
	int mod = 10000;
	while(cin>>a0>>a1>>p>>q>>k) {
		if(k==0) cout<<a0<<endl;
		else if(k==1) cout<<a1<<endl;
		else {
			for(int i=2;i<=k;i++) {
				a2=(q*a0+p*a1)%mod;
				a0=a1;
				a1=a2;
			}
			cout<<a2<<endl;
		}
	}
	return 0;
}