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

    return 0;
}