#include <bits/stdc++.h>
using namespace std;

int main() {
	int a0,a1,p,q,k;
	while(cin>>a0>>a1>>p>>q>>k){
	    int a[k+1];
	    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]<<endl;
	}

}

递归就是最好的迭代