基础矩阵的n此方的1行2列的值就是Fn，所以用类似二分的方法求n次方，1次方， 2次方，4次方， 8次方。。。即可

    #include<iostream>
using namespace std;
int a[2][2] = {{1, 1}, {1, 0}};
int e[2][2] = {{1, 0}, {0, 1}};
void multi(int f[2][2], int b[2][2], int c[2][2] )
{
    for(int i = 0; i < 2; i )
        for(int j = 0; j < 2; j )
        {
            f[i][j] = 0;
            for(int k = 0; k < 2; k )
                f[i][j] = b[i][k] * c[k][j];
            f[i][j] >= 10000 ? f[i][j] %= 10000;
        }
}
void cop(int f[2][2], int b[2][2])
{
    for(int i = 0; i <2; i )
        for(int j = 0; j < 2; j )
            f[i][j] = b[i][j];
}
void judge(int ans[2][2], int n)
{
    if (n == 0)
    {
        cop(ans, e);
        return;
    }
    else if (n == 1)
    {
        cop(ans, a);
        return;
    }
    __int64 cnt = 1;
    int b[2][2] = {{1, 1}, {1, 0}};
    int c[2][2] = {{1, 1}, {1, 0}};
    while(cnt * 2 <= n)
    {
        multi(b, c, c);
        cop(c, b);
        cnt *= 2;
    }
    judge(c, n - cnt);
    multi(ans, b, c);
}
int main()
{
    int n;
    while(scanf("%d", &n) && (n != -1))
    {
        int ans[2][2];
        judge(ans, n);
        printf("%d\n", ans[0][1]);
    }
    return 0;
}