//POJ 3070
/*
 In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …


 Given an integer n, your goal is to compute the last 4 digits of Fn.

 Input

 The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

 Output

 For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).
 */

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

const int MOD = 10000;

struct Matrix {
    int m[2][2];


    Matrix operator * (const Matrix& rhs)
    {
        Matrix matrix = {0, 0, 0, 0};
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                for(int k = 0; k < 2; ++k)
                    matrix.m[i][j] = (matrix.m[i][j] + (m[i][k] * rhs.m[k][j]) % MOD) % MOD;
        return matrix;
    }
}f;

Matrix base = {1, 1, 1, 0};


int pow(Matrix& matrix, int n)
{
    Matrix res = {1, 0, 0, 1};
    while(n)
    {
        if(n & 1)
            res = res * matrix;
        matrix = matrix * matrix;
        n >>= 1;
    }
    return res.m[0][1];
}


int main() {
    int n;
    while(~scanf("%d",&n))
    {
        if(n == -1)break;
        base.m[0][0] = 1;
        base.m[0][1] = 1;
        base.m[1][0] = 1;
        base.m[1][1] = 0;
        printf("%d\n", pow(base, n));
    }
    return 0;
}