#include <bits/stdc++.h>
#define NMAX 10
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int n;
struct tip{long long int a[NMAX][NMAX];};
tip m,rez;
void init();
void inm();
void inm1();
int main()
{fin>>n;
 if(n<=2)
    fout<<1;
   else
{
init();
for(int j=0; (1<<j)<=n-2;j++)
    {
     if( (n-2) & (1<<j))
          inm();
     inm1();
    }
fout<<   (1ll*rez.a[1][2]* 1+rez.a[2][2]*1   )%MOD;
//<< rez.a[1][1]<<" "<<rez.a[1][2]<<'\n';
//fout<< rez.a[2][1]<<" "<<rez.a[2][2]<<'\n';
}
   return 0;
}
void init()
{
  m.a[1][1]=0;
  m.a[1][2]=1;
  m.a[2][1]=1;
  m.a[2][2]=1;
  rez.a[1][1]=1;

  rez.a[1][2]=0;

  rez.a[2][2]=1;

  rez.a[2][1]=0;

}
void inm()
{
 int i,j,k;
 tip rev;
 rev.a[1][1]=rev.a[1][2]=rev.a[2][1]=rev.a[2][2]=0;
 for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            {
             for(k=1;k<=2;k++)
                  rev.a[i][j]= (rev.a[i][j]+  rez.a[i][k] *m.a[k][j])%MOD;
            }
for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
       rez.a[i][j]=rev.a[i][j];
}
void inm1()
{
 int i,j,k;
 tip rev;
 rev.a[1][1]=rev.a[1][2]=rev.a[2][1]=rev.a[2][2]=0;
 for(i=1;i<=2;i++)
        for(j=1;j<=2;j++)
            {
             for(k=1;k<=2;k++)
                  rev.a[i][j]= (rev.a[i][j]+  m.a[i][k] *m.a[k][j])%MOD;
            }
for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
       m.a[i][j]=rev.a[i][j];
}