#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define matrix pair< pair<ll,ll>,pair<ll,ll> >
#define e11 first.first
#define e12 first.second
#define e21 second.first
#define e22 second.second

ifstream f("kfib.in");
ofstream g("kfib.out");

int k;
const int mod=666013;

matrix operator*(matrix A,matrix B)
{
   matrix R;
   R.e11=(A.e11*B.e11+A.e12*B.e21)%mod;
   R.e12=(A.e11*B.e12+A.e12*B.e22)%mod;
   R.e21=(A.e21*B.e11+A.e22*B.e21)%mod;
   R.e22=(A.e21*B.e12+A.e22*B.e22)%mod;
   return R;
}

matrix X,C;

matrix exp(int e)
{
   if(e==1) return {{0,1},{1,1}};
   else if(e==0) return {{1,0},{0,1}};

   C=exp(e>>1);

   C=C*C;

   if(e&1) C=C*X;


   return C;
}

int main()
{
    f>>k;
    X={{0,1},{1,1}};
    C={{1,0},{0,1}};

    C=exp(k);


    g<<C.e12;
    return 0;
}