#include <iostream>
#include <fstream>
using namespace std;
ifstream be("kfib.in");
ofstream ki("kfib.out");
long long MOD=666013;
void szorz(long long (&a)[3][3],long long (&b)[3][3],long long (&c)[3][3])
{
    int sum=0;
    for(int i=1;i<=2;i++)
    {
       for(int j=1;j<=2;j++)
       {
           for(int k=1;k<=2;k++)
                sum+=(a[i][k]*b[k][j])%MOD;
           c[i][j]=sum;
           sum=0;
       }
    }
}
void masol(long long (&a)[3][3],long long (&b)[3][3])
{
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
        b[i][j]=a[i][j];
}
long long d[2][2],l[2][2];
int main()
{
   int k;
   be>>k;
    long long a[3][3],b[3][3],c[3][3];
   a[1][1]=0;
   a[1][2]=1;
   a[2][1]=1;
   a[2][2]=1;
   masol(a,b);
   k--;
   while(k>0)
   {
       if(k%2==0)
       {
           szorz(a,b,c);
           masol(c,b);
       }
       else{ szorz(a,b,c);
       masol(c,b);
       szorz(a,b,c);
       masol(c,b);}k=k/2;
   }
   d[1][1]=0;
   d[1][2]=1;
    for(int i = 1; i <=1 ; ++i)
        for(int j = 1; j <=2; ++j)
            for(int k = 1; k <= 2; ++k)
            {
                l[i][j] += (d[i][k] * c[k][j])%MOD;
            }
ki<<l[1][1];
    return 0;
}