#include <iostream>
#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const long long  mod=666013;
long long k,a[3][3],b[3][3],c[3][3];

void citire(){f>>k;}

void inm(long long  x[3][3],long long  y[3][3],long long  z[3][3])
{
    for(long long  i=1;i<3;i++)
        for(long long  j=1;j<3;j++)
        for(long long  h=1;h<3;h++)
        z[i][j]=(z[i][j]+x[i][h]*y[h][j])%mod;

}
void afisare(long long  x[3][3])
{
    for(long long  i=1;i<3;i++)
        {for(long long  j=1;j<3;j++)g<<x[i][j]<<" ";
    g<<endl;}
}
void putere(long long  p)
{ long long  i;
    for(i=0;(1<<i)<=p;i++)
     {if((1<<i)&p)
     {c[1][1]=0;c[1][2]=0;c[2][1]=0;c[2][2]=0;
         inm(a,b,c);
         a[1][1]=c[1][1];a[1][2]=c[1][2];a[2][1]=c[2][1];a[2][2]=c[2][2];
     }
     c[1][1]=0;c[1][2]=0;c[2][1]=0;c[2][2]=0;
     inm(b,b,c);
     b[1][1]=c[1][1];b[1][2]=c[1][2];b[2][1]=c[2][1];b[2][2]=c[2][2];
     }
}
int main()
{
    citire();
a[1][1]=1;
a[2][2]=1;

b[1][1]=0;
b[1][2]=1;
b[2][1]=1;
b[2][2]=1;


    putere(k-1);

    g<<a[2][2];


    return 0;
}