矩阵快速幂入门题。并且转移矩阵直接题目给你了...
那么模拟矩阵操作就好了。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

struct mat {
    ll a[2][2];
    mat() {memset(a, 0, sizeof(a));}
    mat operator * (mat x) {
        mat ans;
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                for(int k = 0; k < 2; ++k) {
                    (ans.a[i][j] += a[i][k] * x.a[k][j]) %= 10000;
                }
            }
        }
        return ans;
    }
    mat pow(mat a, ll t) {
        mat ans;
        ans.a[0][0] = ans.a[1][1] = 1;
        while(t) {
            if(t & 1) ans = ans * a;
            a = a * a; t >>= 1;
        }
        return ans;
    }
};

int main() {
    ll n;
    mat A; A.a[0][0] = A.a[0][1] = A.a[1][0] = 1;
    while(~scanf("%lld", &n) && n != -1) {
        mat F; F.a[0][0] = 1; F.a[0][1] = 1;
        if(!n) {puts("0"); continue;}
        if(n == 1) {puts("1"); continue;}
        F = F * F.pow(A, n - 2);
        printf("%lld\n", F.a[0][0]);
    }
}