#include<iostream>
#include<fstream>
using namespace std;
long long int a[4][4];
long long int r[4][4];
long long int c[4][4];
int m=666013;
void ButterMeUpSpaceMan()
{
    int b[4][4];
       b[0][0]=a[0][0];
   b[0][1]=a[0][1];
   b[1][0]=a[1][0];
   b[1][1]=a[1][1];
    for(int x=0;x<2;x++)
        for(int y=0;y<2;y++){
        c[x][y]=0;
          for(int z=0;z<2;z++)
    {
        c[x][y]+=(1LL*a[x][z]*b[z][y])%m;
        c[x][y]%=m;
    }
        }
    for(int x=0;x<2;x++)
        for(int y=0;y<2;y++)
            a[x][y]=c[x][y];
}
void ButterMeUpSpaceManPart2()
{
    for(int x=0;x<2;x++)
        for(int y=0;y<2;y++){
         c[x][y]=0;
          for(int z=0;z<2;z++)
    {
        c[x][y]+=1LL*a[x][z]*r[z][y]%m;
    c[x][y]%=m;
    }
        }
    for(int x=0;x<2;x++)
        for(int y=0;y<2;y++)
            r[x][y]=c[x][y];
}
void exp(int n)
{
   while(n>0)
   {
       if(n%2)
       {
        ButterMeUpSpaceManPart2();
        n--;
       }
       else
       {
           ButterMeUpSpaceMan();
           n/=2;
       }
   }
}
int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
   long long int n;
   f>>n;
   a[0][0]=0;
   a[0][1]=1;
   a[1][0]=1;
   a[1][1]=1;
   r[0][0]=1;
   r[0][1]=0;
   r[1][0]=0;
   r[1][1]=1;
   exp(n-2);
   g<<r[1][0]+r[1][1];
}