#include <fstream>
#define p 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

void putere(int&a,int&b,int&c,int&d,int n)
{int a1=a,b1=b,c1=c,d1=d;
int a2,b2,c2,d2;
if(n>1)
   if(n%2==1)
      {putere(a,b,c,d,n-1);
       a2=a,b2=b,c2=c,d2=d;
       a=(1LL*a1*a2%p+1LL*b1*c2%p)%p;
       b=(1LL*a1*b2%p+1LL*b1*d2%p)%p;
       c=(1LL*a2*c1%p+1LL*d1*c2%p)%p;
       d=(1LL*c1*b2%p+1LL*d1*d2%p)%p;
      }
  else
      {a=(1LL*a1*a1%p+1LL*b1*c1%p)%p;
       b=(1LL*a1*b1%p+1LL*b1*d1%p)%p;
       c=(1LL*a1*c1%p+1LL*d1*c1%p)%p;
       d=(1LL*c1*b1%p+1LL*d1*d1%p)%p;
       putere(a,b,c,d,n/2);
      }
}


int main()
{int k,a,b,c,d;
fin>>k;
a=0; b=c=d=1;
putere(a,b,c,d,k);
fout<<(b)%p<<" ";
return 0;
}