#include <iostream>
#include <fstream>

using namespace std;

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

#define mod 666013
int k;
struct matrice{int a=0,b=0,c=0,d=0;} A;

/// rezultatul ramane in X
matrice inmult(matrice X, matrice Y)
{
    matrice rez;
    rez.a = ((1ll*X.a*Y.a%mod) + (1LL*X.b*Y.c%mod)) % mod;
    rez.b = ((1ll*X.a*Y.b%mod) + (1LL*X.b*Y.d%mod)) % mod;
    rez.c = ((1ll*X.c*Y.a%mod) + (1LL*X.d*Y.c%mod)) % mod;
    rez.d = ((1ll*X.c*Y.b%mod) + (1LL*X.d*Y.d%mod)) % mod;
    return rez;
}

void lgput(matrice &A, int poww)
{
    matrice rez;
    rez.a = rez.d = 1;
    for(; poww; poww>>=1)
    {
        if(poww&1)
            rez = inmult(rez, A);
        A = inmult(A,A);
    }
    A = rez;
}

int main()
{
    fin>>k;
    if(k==0)    fout<<0;
    else if(k==1)   fout<<1;
    else
    {
        A.b = A.c = A.d = 1;
        lgput(A, k-1);
        fout<<A.d%mod;
    }

    fin.close();
    fout.close();
    return 0;
}