poj3070

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
using namespace std;
const int N = 5e5 + 5;
#define all(s) s.begin(),s.end()
const int M = 1005;
const int mod = 10000;
typedef long long ll;
#define endl "\n"
struct Matrix{
    int a[M][M],n , m;
    Matrix(int _n,int _m,bool dy){
        n = _n;
        m = _m;
        memset(a , 0 , sizeof a);
        if (dy) for (int i = 0 ; i < n; i++) a[i][i] = 1;
    }
};
Matrix operator + (const Matrix & a, const Matrix &b){
    Matrix c(a.n , a.m , 0);
    int n = a.n , m = b.m;
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < m ; j ++) c.a[i][j] = (a.a[i][j] + b.a[i][j]) % mod;
    }
    return c;
}
Matrix operator * (const Matrix & a, const Matrix &b){
    ll m = a.n , n = a.m , p = b.m;
    Matrix res(b.n,b.m,0);
    for (int i = 0 ; i < m ; i ++) {
        for (int k = 0 ; k < n ; k ++) {
            if (a.a[i][k] == 0) continue;
            for (int j = 0 ; j < p ; j ++){
                res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
            }
        }
    }
    return res;
}
Matrix operator ^ (Matrix base,int n){
    Matrix res(base.n , base.m , 1);
    while (n){
        if (n & 1) res = res * base;
        base = base * base;
        n >>= 1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    Matrix base(2 , 2 , 0);
    int n;
    while (cin >> n && n != -1){
        if (n == 0){
            cout << -1 << endl;
            continue;
        }
        base.a[0][0] = 1,base.a[0][1] = 1;
        base.a[1][0] = 1,base.a[1][1] = 0;
        Matrix ans = base^n;
        cout << ans.a[0][1] << endl;
    }
    return 0;
}