#include<cstdio>
#include<cstring>

const int MOD=666013;

void inmultire(int rasp[2][2],int a[2][2],int b[2][2])
{
 for(int i=0;i<2;i++)
     for(int j=0;j<2;j++)
         for(int k=0;k<2;k++)
             rasp[i][j]=(rasp[i][j]+(1LL*a[i][k]*b[k][j])%MOD)%MOD;
}

void copiere(int source[2][2],int destination[2][2])
{
 memcpy(destination,source,4*(sizeof (int)));
}

void put(int a[2][2],int rasp[2][2],int k)
{
 if(k==0)
    {
     rasp[0][0]=rasp[1][1]=1;
     return;
    }
 if(k==1)
    {
     copiere(a,rasp);
     return;
    }
 int b[2][2],c[2][2];
 memset(b,0,sizeof b);
 memset(c,0,sizeof c);
 put(a,b,k/2);
 inmultire(c,b,b);
 if(k%2==1)
    inmultire(rasp,a,c);
 else
    copiere(c,rasp);
}

int Z[2][2]={{0,1},{1,1}};
int M0[2][2]={{1,1},{0,0}};

int main()
{
 FILE *in=fopen("kfib.in","r");
 int k;
 fscanf(in,"%d ",&k);
 fclose(in);
 int rasp[2][2],aux[2][2];
 memset(rasp,0,sizeof rasp);
 put(Z,rasp,k-1);
 copiere(rasp,aux);
 memset(rasp,0,sizeof rasp);
 inmultire(rasp,M0,aux);
 FILE *out=fopen("kfib.out","w");
 fprintf(out,"%d\n",rasp[0][0]);
 fclose(out);
 return 0;
}