#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int m=666013;
long long i[3][3],n;
void inmultire(long long a[3][3], long long b[3][3])
{
    long long c[3][3];
    c[1][1]=(a[1][1]*b[1][1]%m+a[1][2]*b[2][1]%m)%m;
    c[1][2]=(a[1][1]*b[1][2]%m+a[1][2]*b[2][2]%m)%m;
    c[2][1]=(a[2][1]*b[1][1]%m+a[2][2]*b[2][1]%m)%m;
    c[2][2]=(a[2][1]*b[1][2]%m+a[2][2]*b[2][2]%m)%m;
    a[1][1]=c[1][1];
    a[1][2]=c[1][2];
    a[2][1]=c[2][1];
    a[2][2]=c[2][2];
}
void lgput(long long i[3][3], int n)
{
    long long matr[3][3];
    matr[1][1]=0;
    matr[1][2]=matr[2][1]=matr[2][2]=1;
    i[1][1]=i[2][2]=1;
    i[1][2]=i[2][1]=0;
    while(n!=0)
    {
        if((n&1)==1)
        {
            inmultire(i,matr);
        }
        inmultire(matr,matr);
        n=n>>1;
    }
}
int main()
{
   fin>>n;
   if(n==0)
   {
       fout<<0;
       return 0;
   }
   if(n==1)
   {
       fout<<1;
       return 0;
   }
   if(n>=2)
   {
       lgput(i,n-1);
       fout<<i[2][2]%m;
       return 0;
   }
   fin.close();
   fout.close();
}