学步园

/*

很水的矩阵题，没什么说的... 

*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct matrix{
     long long a[3][3];
}A,B;

matrix mult2(matrix A,matrix B){  /// 矩阵乘法 
    matrix C;
    for(int i=1;i<=2;i++){   /// 第一个矩阵的行 
        for(int j=1;j<=2;j++){    /// 第二个矩阵的列 
            C.a[i][j]=0;
            for(int k=1;k<=2;k++){  /// 第二个矩阵的行 或者 第一个矩阵的列 
                C.a[i][j] = (C.a[i][j] + A.a[i][k]*B.a[k][j])%10000;
            }        }
    }
    return C;
}

matrix mult(matrix A,long long n){  ///  二分快速幂 
    if(n==1) return A;
    A = mult(A,n/2);
    if(n%2==0)  return  A = mult2(A,A);
    return  A = mult2(mult2(A,A),B);
}

int main(){
    long long  n;
    while(scanf("%lld",&n)!=EOF){
        if(!n) { printf("0\n"); continue; }
        if(n == -1) break;
        A.a[1][1]=1; A.a[1][2]=1;
        A.a[2][1]=1; A.a[2][2]=0;
        B = A;
        A = mult(A,n); 
        printf("%lld\n",A.a[1][2]%10000);
    }
}