1 #include
2 #include
3 #include
4 using namespace std;
5 const int mod=10000;
6 int n;
7 struct matrix
8 {
9 int data[2][2];
10 matrix operator*(matrix &b)
11 {
12 matrix c;
13 memset(c.data,0,sizeof(c.data));
14 for(int i=0;i<2;i++)
15 for(int j=0;j<2;j++)
16 for(int k=0;k<2;k++)
17 c.data[i][j]=(c.data[i][j]+this->data[i][k]*b.data[k][j])%mod;
18 return c;
19 }
20 }ans,base;
21 int quipow(int n)
22 {
23 memset(ans.data,0,sizeof(ans.data));
24 memset(base.data,0,sizeof(base.data));
25 ans.data[0][0]=0;ans.data[0][1]=1;
26 base.data[0][1]=base.data[1][0]=base.data[1][1]=1;
27 while(n)
28 {
29 if(n&1)ans=ans*base;
30 n>>=1;
31 base=base*base;
32 }
33 return ans.data[0][0];
34 }
35
36 int main()
37 {
38 while(~scanf("%d",&n)&&~n)
39 {
40 printf("%d\n",quipow(n));
41 }
42 return 0;
43 }