#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 10000
using namespace std;
long long n;

//矩阵快速幂：
struct matrix
{
    int a[2][2];
};

matrix multiply(matrix x,matrix y)
{
    matrix temp;
    memset(temp.a,0,sizeof(temp.a));
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++)
            {
                for(int k=0;k<2;k++)
                {
                    temp.a[i][j] += (x.a[i][k] * y.a[k][j] )% mod;
                }
                temp.a[i][j] %= mod;
            }
    }
    return temp;
}
matrix quickpow(long long n)
{
    matrix E = {1,0,
                0,1};
    matrix M = {1,1,
                1,0};
       while (n >= 1)
       {
             if (n & 1)
                E = multiply(E,M);
             n = n >> 1;
             M = multiply(M,M);
       }
       return E;
}

int main()
{
    matrix temp;
    memset(temp.a,0,sizeof(temp.a));
    while(~scanf("%d", &n))
    {
        if (n == -1)
        {
            break;
        }
        if (n == 0)
        {
            printf("0\n");
            continue;
        }
        temp = quickpow(n);
        printf("%d\n" , temp.a[0][1]);
    }
    return 0;
}