#include <fstream>
#define MOD  666013

using namespace std;
long long k;
int a[3][3],b[3][3];

void copy_mat(int a[3][3],int b[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a[i][j]=b[i][j];
}

void inm_mat(int a[3][3],int b[3][3])
{
    int c[3][3];
    long long s;
    int x;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
    {
        s=0;
        for(x=1;x<=2;x++)
            s+=(1LL*a[i][x]*b[x][j]);
        c[i][j]=s%MOD;
    }

    copy_mat(a,c);
}

void rezolvare(int a[3][3],int p)
{
    int c[3][3];
    c[1][1]=0;
    c[2][1]=c[2][2]=c[1][2]=1;
    while(p)
    {
        if(p%2==1) inm_mat(c,a);
        inm_mat(a,a);
        p/=2;
    }
    copy_mat(a,c);
}
int main()
{
   ifstream fin("kfib.in");
   ofstream fout("kfib.out");
   b[1][2]=1;
   a[1][2]=a[2][1]=a[2][2]=1;
   fin>>k;
   if(k==0) fout<<'0\n';
   else
   {    rezolvare(a,k-2);
        inm_mat(b,a);
        fout<<b[1][2]<<'\n';

   }
   fin.close();
   fout.close();
    return 0;
}