#include <iostream>#include <string.h>#include <stdlib.h>#include <cstdio>#include <algorithm>#define mod 10000using namespace std;struct m{    int a[3][3];} init,res;int n;m Mult(m x,m y){    m tmp;    for(int i=0; i<2; i++)    {        for(int j=0; j<2; j++)        {            tmp.a[i][j]=0;            for(int k=0; k<2; k++)            {                tmp.a[i][j]=(tmp.a[i][j]+x.a[i][k]*y.a[k][j])%mod;            }        }    }    return tmp;}m Pow(m x,int n){    m tmp;    for(int i=0; i<2; i++)    {        for(int j=0; j<2; j++)        {            tmp.a[i][j]=(i==j);        }    }    while(n)    {        if(n&1) tmp=Mult(tmp,x);        n>>=1;        x=Mult(x,x);    }    return tmp;}int main(){    while(scanf("%d",&n)!=EOF)    {        if(n==-1) break;        init.a[0][0]=1;        init.a[0][1]=1;        init.a[1][0]=1;        init.a[1][1]=0;        res=Pow(init,n);        cout<<res.a[1][0]<<endl;    }    return 0;}