#include<iostream>
#include<cstring>
using namespace std;
const int mod=10000;
int n;
void mul(int a[][2], int f[][2])
{
    int c[2][2]={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)
            {
                c[i][j] = (c[i][j] + a[i][k] * f[k][j]) % mod;
            }
        }
    }
    memcpy(a, c, sizeof(c));
}
int fib(int n)
{
    int a[][2] = {0, 1, 0, 0};
    int f[][2] = {0, 1, 1, 1};
    while(n)
    {
        if(n & 1) mul(a, f);
        mul(f, f);
        n >>= 1;
    }
    return a[0][0];
}
int main()
{
    while(cin >> n, n != -1) cout << fib(n) << endl;
    return 0;
}