#include<iostream>
#include<fstream>
using namespace std;

   long int M = 666013;

   ifstream f("kfib.in");
   ofstream g("kfib.out");
   void inmultire(long int u[4][4], long int v[4][4], long int a[4][4])
   {
	   u[1][1] = (v[1][1] * a[1][1] + v[1][2] * a[2][1]) % M;
	   u[1][2] = (v[1][1] * a[1][2] + v[1][2] * a[2][2]) % M;
	   u[2][1] = (v[2][1] * a[1][1] + v[2][2] * a[2][1]) % M;
	   u[2][2] = (v[2][1] * a[1][2] + v[2][2] * a[2][2]) % M;
   }

   void putere(long int rezultat[4][4], long int z[4][4], long int n)
   {long int rezultat1[4][4], aux[4][4];
     long int i,j;
      if (n==1)
         for(i=1;i<=2;i++)
            for(j=1;j<=2;j++)
               rezultat[i][j] = z[i][j];
      if (n==0)
         {
         rezultat[1][1]=1;
         rezultat[1][2]=0;
         rezultat[2][1]=0;
         rezultat[2][2]=1;
         }
      else 
         { 
            if (n%2==0)
               {
               putere(rezultat1, z, (n/2));
               inmultire(rezultat,rezultat1,rezultat1);
               }
            else
            {
            putere(rezultat1, z, (n/2));
            inmultire(aux, rezultat1, rezultat1);
            inmultire(rezultat, aux, z);
            }
         }
   }

int main()
{
   long int u[4][4], a[4][4];
   long int N;
   f>>N;
   a[1][1]=0;
   a[1][2]=1;
   a[2][1]=1;
   a[2][2]=1;
   putere(u, a, N);
   
   long int f[4][4];
   f[1][1] = 0;
   f[1][2] = 1;
   f[2][1] = 0;
   f[2][2] = 1;
   long int produs[4][4];
   
   inmultire(produs,f,u);
         g<<(produs[1][1] % M);
return 0;
}