#include<iostream>
using namespace std;
/*__int64 Montgomery(__int64 n, __int64 p, __int64 m)
{ // 快速计算 (n ^ p) % m 的值，与power算法极类似
    __int64 r = n % m; // 这里的r可不能省
    __int64 k = 1;
    while (p > 1)
    {
        if ((p & 1)!=0)
        {
            k = (k * r) % m; // 直接取模
        }
        r = (r * r) % m; // 同上
        p /= 2;
    }
    return (r * k) % m; // 还是同上
}*///这是先前的版本

void fen(int r[][2],int k[][2])
{
   int ans[2][2];
   ans[0][0]=(r[0][0]*k[0][0]%10000+r[0][1]*k[1][0]%10000)%10000;
   ans[0][1]=(r[0][0]*k[0][1]%10000+r[0][1]*k[1][1]%10000)%10000;
   ans[1][0]=(r[1][0]*k[0][0]%10000+r[1][1]*k[1][0]%10000)%10000;
   ans[1][1]=(r[1][0]*k[0][1]%10000+r[1][1]*k[1][1]%10000)%10000;
   r[0][0]=ans[0][0],r[0][1]=ans[0][1],r[1][0]=ans[1][0],r[1][1]=ans[1][1];
}
int fbnq(int num)
{
   int k[2][2]={1,0,0,1};
   int r[2][2]={1,1,1,0};
	while(num>1)
	{
		if((num&1)!=0)
		{
             fen(k,r);
		}
		fen(r,r);
        num/=2;
	}
	fen(r,k);
	return r[0][1];
}//仿照他写的版本


int main()
{
	int num;
	while(cin>>num&&num!=-1)
	{
		if(num==0)
			cout<<0<<endl;
		else
            cout<<fbnq(num)<<endl;
	}
	return 0;
}