#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");
unsigned long long k, a[2][2],b[2][2];
#define MOD 666013

void inmultire( unsigned long long a[2][2] , unsigned long long b[2][2] , unsigned long long c[2][2] )
{
    unsigned long long d[2][2];
    d[0][0]=( (a[0][0]*b[0][0])%MOD + a[0][1]*b[0][1] )%MOD;
    d[0][1]=( (a[0][0]*b[0][1])%MOD +(a[0][1]*b[1][1])%MOD )%MOD;
    d[1][0]=( (a[1][0]*b[0][0])%MOD + (a[1][1]*b[1][0])%MOD )%MOD;
    d[1][1]=((a[0][1]*b[0][1])%MOD + (a[1][1]*b[1][1])%MOD  )%MOD;

    c[0][0]=d[0][0];c[0][1]=d[0][1];c[1][0]=d[1][0];c[1][1]=d[1][1];


}
void alan(unsigned long long a[2][2] , unsigned long long b[2][2] , unsigned long long n )

{
     if(n==0)
     {
         b[0][0]=b[1][1]=0;
         b[0][1]=b[1][0]=1;
     }

          else if(n==1)
         {
             b[0][0]=a[0][0];
             b[0][1]=a[0][1];
             b[1][0]=a[1][0];
             b[1][1]=a[1][1];
         }

    else
    {
        unsigned long long c[2][2];
        alan(a,c,n/2);
        if(n%2==0) inmultire(c,c,b);
        else
            {
            inmultire(c,c,b);
             inmultire(b,a,b);
            }
    }
}
int main()
{
   f>>k;
   a[0][0]=0;
   a[1][0]=1;
   a[0][1]=1;
   a[1][1]=1;
   alan(a,b,k-1);
    if(b[1][1] < 0) b[1][1]+=MOD;
    g<<b[1][1]<<'\n';

   f.close();
   g.close();
    return 0;
}