using namespace std;
int n,a[1000001]={1,1,2},b[1000001]={1,1,2};
long long f(long long x);
long long g(long long x);
int main()
{
    cin >> n;
	printf("%lld",f(n)%10000);
	return 0;
}
long long f(long long  x){
	if(b[x])return b[x];
    b[x]=(2*(g(x-2)%10000)%10000+(f(x-1)%10000+f(x-2)%10000)%10000)%10000;
    return b[x];
} 
long long g(long long x){
	if(a[x])return a[x];
	a[x]=(f(x-2)%10000+g(x-1)%10000)%10000;
	return a[x];
}

全WA了。。。