#include <bits/stdc++.h>

using namespace std;

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

int k;
const int mod=666013;

struct matrice{
    int mat[5][5];
}a,nul;

void produs(matrice &a,matrice b)
{
    matrice rez;
    rez=nul;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int t=0; t<2; t++)
                rez.mat[i][j]=(1ll*rez.mat[i][j]+1ll*a.mat[i][t]*b.mat[t][j]%mod)%mod;
    a=rez;
}

int power(int b)
{
    matrice rez;
    rez=nul, rez.mat[0][0]=rez.mat[1][1]=1;
    while(b)
    {
        if(b&1)
            produs(rez,a);
        produs(a,a);
        b>>=1;
    }
    return rez.mat[0][0];
}

int32_t main()
{
    f>>k;
    a.mat[0][0]=a.mat[0][1]=a.mat[1][0]=1;
    g<<power(k-1);
    return 0;
}