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

template<typename T>
inline T read()
{
	T x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=3;
const int mod=10000;
long long n;

struct matrix
{
	int n,m;
	long long a[MAXN][MAXN];
	
	inline matrix(){n=m=0;memset(a,0,sizeof(a));}
	
	inline void init(int n)
	{
		this->n=n;this->m=n;
		for (int i=1;i<=n;i++) a[i][i]=1;
	}
	
	inline struct matrix operator * (struct matrix tmp)
	{
		struct matrix ans;
		ans.n=n;ans.m=tmp.m;
		for (int i=1;i<=ans.n;i++)
			for (int j=1;j<=ans.m;j++)
				for (int k=1;k<=tmp.n;k++)
					ans.a[i][j]=(ans.a[i][j]+a[i][k]*tmp.a[k][j]%mod)%mod;
		return ans;
	}
}f;

inline struct matrix qpow(struct matrix a,long long b)
{
	struct matrix res;res.init(2);
	while (b)
	{
		if (b&1) res=res*a;
		a=a*a;b>>=1;
	}
	return res;
}

int main()
{
	f.m=2;f.n=2;
	f.a[1][1]=1;f.a[1][2]=1;
	f.a[2][1]=1;f.a[2][2]=0;
	while (true)
	{
		n=read<long long>();
		if (n==-1) break;
		printf("%d\n",qpow(f,n).a[1][2]);
	}
	return 0;
}