#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

const int mod = 666013;

vector <int> v;

unsigned long long k, A[5], B[5], Zc[5];

void pat (int x)
{
    if (x==1)
    {
        B[1]=(A[1]*A[1]%mod+A[2]*A[3]%mod)%mod;
        B[2]=(A[1]*A[2]%mod+A[2]*A[4]%mod)%mod;
        B[3]=(A[3]*A[1]%mod+A[4]*A[3]%mod)%mod;
        B[4]=(A[3]*A[2]%mod+A[4]*A[4]%mod)%mod;
    }
    if (x==0)
    {
        B[1]=(A[1]*Zc[1]%mod+A[2]*Zc[3]%mod)%mod;
        B[2]=(A[1]*Zc[2]%mod+A[2]*Zc[4]%mod)%mod;
        B[3]=(A[3]*Zc[1]%mod+A[4]*Zc[3]%mod)%mod;
        B[4]=(A[3]*Zc[2]%mod+A[4]*Zc[4]%mod)%mod;
    }
    A[1]=B[1]; A[2]=B[2]; A[3]=B[3]; A[4]=B[4];
}

void exp (int k)
{
    if (k==1);
    else if (k%2==0) {exp(k/2); pat(1);}
    else {exp(k-1); pat(0);}
}

int main()
{
    fin >> k;
    A[1]=Zc[1]=0; A[2]=A[3]=A[4]=Zc[2]=Zc[3]=Zc[4]=1;
    exp(k-1);
    fout << A[4];
}