学步园

#include<iostream>
#include<algorithm>
#include<string.h>
#include<stack>
#include<queue>
#include<math.h>
#include<cstdio>

using namespace std;
const int mod=10000;

struct Matrix
{
	int m[15][15];	
}num;

Matrix mul(Matrix m1,Matrix m2)
{
	Matrix ans;	
	memset(ans.m,0,sizeof(ans.m));
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				ans.m[i][j]=(ans.m[i][j]+m1.m[i][k]*m2.m[k][j])%mod;	
	return ans;
}

Matrix pow(Matrix m1,int b)
{
	Matrix ans;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
			ans.m[i][j]=(i==j?1:0);
	while(b)
	{
		if(b&1)
			ans=mul(ans,m1);
		m1=mul(m1,m1);
		b/=2;
	}
	return ans;
}


int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		if(n==-1) break;
		memset(num.m,0,sizeof(num.m));	
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				num.m[i][j]=1;
		num.m[1][1]=0;
		num=pow(num,n);
		printf("%d\n",num.m[1][0]);
	}
	return 0;
}