#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define mod 10000using namespace std;struct m{    int a[3][3];} init,res;int n;m Mult(m x,m y){    m tmp;    for(int i=0; i<2; i++)    {        for(int j=0; j<2; j++)        {            tmp.a[i][j]=0;            for(int k=0; k<2; k++)            {                tmp.a[i][j]=(tmp.a[i][j]+x.a[i][k]*y.a[k][j])%mod;            }        }    }    return tmp;}m Pow(m x,int n){    m tmp;    for(int i=0; i<2; i++)//将矩阵tmp初始化成单位矩阵[1,0]    {        for(int j=0; j<2; j++)//                  [0,1]        {            tmp.a[i][j]=(i==j);        }    }    while(n)    {        if(n&1) tmp=Mult(tmp,x);        n>>=1;        x=Mult(x,x);    }    return tmp;}int main(){    while(scanf("%d",&n)!=EOF)    {        if(n==-1) break;        init.a[0][0]=1;        init.a[0][1]=1;        init.a[1][0]=1;        init.a[1][1]=0;        res=Pow(init,n);        cout<
          
           <