题目很简单。
注意初始化，一开始没有初始化，然后就错了。悲伤。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define Nnum 31
#define Mnum 31
#define LL long long
struct matrix
{int mat[3][3];matrix(){memset(mat,0,sizeof(mat));}
};
matrix mul(matrix A,matrix B)
{matrix C;int i,j,k;for(i=1; i<=2; i++){for(j=1; j<=2; j++){for(k=1; k<=2; k++){C.mat[i][j]=(C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%10000;}}}return C;
}
matrix powmul(matrix A,int k)
{matrix B;B.mat[1][1]=B.mat[2][2]=1;while(k>=1){if(k&1)B=mul(B,A);A=mul(A,A);k=k/2;}return B;
}
int main()
{int n;matrix A;while(~scanf("%d",&n)&&(n+1)){A.mat[1][1]=A.mat[1][2]=A.mat[2][1]=1;A.mat[2][2]=0;A=powmul(A,n);cout<<A.mat[1][2]<<endl;}return 0;
}