#include <iostream>#include <cstdio>using namespace std;int n=2,M=10000;struct Matrax {    int m[35][35];}; Matrax a,per; void initial(){    int i,j;    for(i=0;i<n;i++){        for(j=0;j<n;j++){            per.m[i][j]=(i==j);        }    }    a.m[0][0]=a.m[0][1]=a.m[1][0]=1;    a.m[1][1]=0;} Matrax multi(Matrax a,Matrax b){    Matrax c;    int k,i,j;    for(i=0;i<n;i++){        for(j=0;j<n;j++){            c.m[i][j]=0;            for(k=0;k<n;k++){                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;            }            c.m[i][j]%=M;        }    }    return c;} Matrax Power(int k){    Matrax c,p,ans=per;    p=a;    while(k){        if(k&1){            ans=multi(ans,p);            k--;        }        else {            k/=2;            p=multi(p,p);        }    }    return ans;}int main(){	int k;	initial();	while(scanf("%d",&k)!=EOF){		if(k==-1) break;		Matrax ans=Power(k);		printf("%d\n",ans.m[0][1]);	}	return 0;}