include[HTML_REMOVED]
define mod 10000
using namespace std;
typedef long long ll;
int cnt=0;
ll ans[105];
void mul(ll a[2][2],ll b[2][2])
{
ll c[2][2]={0};
for(int i=0;i<2;i)
{
for(int j=0;j<2;j)
{
for(int k=0;k<2;k)
c[i][j]=(a[i][k]*b[k][j]%mod+c[i][j]%mod)%mod;
}
}
for(int i=0;i<2;i)
for(int j=0;j<2;j)
a[i][j]=c[i][j];
}
ll fib(int x)
{
ll a[2][2]={0,1,0,0},b[2][2]={0,1,1,1};
while(x)
{
if(x&1) mul(a,b);
mul(b,b);
x>>=1;
}
return a[0][0];
}
int main()
{
int n;
while(cin>>n,n!=-1) ans[cnt]=fib(n);
for(int i=1;i<=cnt;i++)
cout<<ans[i]<<endl;
return 0;
}