中间加不加%10000都是wrong..

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
ll a0,a1,p,q,k;
ll dp[1000];


ll ditui(int k){

	if(k==0)return a0;
	if(k==1)return a1;
	if(dp[k]!=-1)return dp[k];	
	else{
		dp[k]=(p*ditui(k-1)+(q*ditui(k-2)))%10000;
	return dp[k];
	}
	
}	

int main() {
	
	memset(dp,-1,sizeof(dp));
	while(cin>>a0>>a1>>p>>q>>k){
//	dp[0]=a0;
//	dp[1]=a1;
//	for(int i=2;i<=k;i++){
//		dp[i]=((dp[i-1]*p%10000)+(q*dp[i-2])%10000)%10000;
//
//	}
	cout<<ditui(k)<<endl;
	//cout<<dp[k]<<endl;
	}
	return 0;
}