Contest1342/H.cpp

#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
 
struct Mat {
    static const int MOD = 10000;
    static const LL M = 2;
    LL v[M][M];
 
    Mat() { memset(v, 0, sizeof(v)); }
 
    void eye() { FOR(i, 0, M)v[i][i] = 1; }
 
    LL *operator[](LL x) { return v[x]; }
 
    const LL *operator[](LL x) const { return v[x]; }
 
    Mat operator*(const Mat &B) {
        const Mat &A = *this;
        Mat ret;
        FOR (k, 0, M)
            FOR (i, 0, M) if (A[i][k])
                    FOR (j, 0, M)ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
        return ret;
    }
 
    Mat pow(LL n) const {
        Mat A = *this, ret;
        ret.eye();
        for (; n; n >>= 1, A = A * A)
            if (n & 1) ret = ret * A;
        return ret;
    }
 
    Mat operator+(const Mat &B) {
        const Mat &A = *this;
        Mat ret;
        FOR (i, 0, M)FOR (j, 0, M)ret[i][j] = (A[i][j] + B[i][j]) % MOD;
        return ret;
    }
 
    void prt() const {
        FOR (i, 0, M)FOR (j, 0, M)printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
    }
};
 
 
int main() {
    Mat m;
    m[0][0] = m[0][1] = m[1][0] = 1;
    m[1][1] = 0;
 
    for (int n; cin >> n and n != -1;) {
        if (n == 0) {
            cout << 0 << endl;
            continue;
        }
        cout << m.pow(n - 1)[0][0] << endl;
    }
 
    return 0;
}