//PKU 3070 ,calculate Fibonacci
#include <iostream>
#include<stack>
int FPM(int);//fast-power-modulus function declare
using namespace std;
const int Mod=10000;
int main(int argc, char *argv[])
{
int n=0;
while(scanf("%d",&n))
{
if(n==-1)
break;
printf("%d\n",FPM(n));
}
return 0;
}
int FPM(int n)//fast-power-modulus function
{
int matr[4]={1,0,0,1};//initialize matrix
stack<bool>dec;//stack to store binary digit
while(n)//resolve n to binary digit
{
dec.push(1&n);//get the last binary digit
n>>=1;
}
while(!dec.empty())
{
//matrix square
matr[1]=((matr[0]+matr[3])*matr[1])%Mod;
matr[0]=(matr[0]*matr[0]+matr[2]*matr[2])%Mod;
matr[3]=(matr[3]*matr[3]+matr[2]*matr[2])%Mod;
matr[2]=matr[1];
//matrix multiply,
if(dec.top())
{
matr[0]=(matr[0]+matr[1])%Mod;
matr[1]=(matr[1]+matr[3])%Mod;
matr[3]=matr[2];
matr[2]=matr[1];
}
dec.pop();
}
return matr[1];//matr[1] is the result F[N]
}