1 //3070 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5  6 using namespace std; 7  8 struct Matrix 9 {10     int v[2][2];11 };12 int n;13 14 Matrix matrix_mul(Matrix a,Matrix b)15 {16     Matrix c;17     for(int i = 0 ; i < 2 ; i++)18     {19         for(int j = 0 ; j < 2 ; j++)20         {21             c.v[i][j] = 0 ;22             for(int k = 0 ; k < 2 ; k++)23                 c.v[i][j]=(c.v[i][j]+a.v[i][k]*b.v[k][j])%10000;24         }25     }26     return c;27 }28 29 int matrix_mi()30 {31         Matrix p,t ;32         p.v[0][0] = p.v[0][1] = p.v[1][0] = 1 ;33         p.v[1][1] = 0;34         t.v[0][0] = t.v[1][1] = 1 ;//t是单位向量35         t.v[0][1] = t.v[1][0] = 0 ;36         while(n)37         {38             if(n&1)//奇数39                 t = matrix_mul(t,p);40             n = n>>1 ;41             p = matrix_mul(p,p);42         }43         return t.v[1][0] ;44 }45 int main()46 {47     while(scanf("%d",&n)!=EOF&&n!=-1)48     {49         if(n == 0 || n == 1)50         {51             cout<<n<<endl;52             continue;53         }54         int ans = matrix_mi();55         cout<<ans<<endl;56     }57     return 0;58 }