#include <bits/stdc++.h>
#define Mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef long long ll;
ll p;

struct Matrice
{
    ll elem[3][3];
};

Matrice X,I;

void citire(ll &n)
{
    f>>n;
}

void init()
{
    I.elem[1][1]=I.elem[2][2]=1;
    I.elem[2][1]=I.elem[1][2]=0;

    X.elem[1][1]=X.elem[1][2]=X.elem[2][1]=1;
    X.elem[2][2]=0;
}

Matrice Inmultire(Matrice A,Matrice B)
{
    Matrice C;
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
    {
        ll suma=0;
        for(int k=1;k<=2;k++)
            suma+=((A.elem[i][k]%Mod)*(B.elem[k][j]%Mod))%Mod;
        C.elem[i][j]=suma;
    }
    return C;
}

Matrice Exponentiere(ll n)
{
    Matrice R=I;
    while(n > 0 )
    {
        if( ( n & 1 ) > 0 )
            R=Inmultire(R,X);

        X=Inmultire(X,X);
        n>>=1;
    }
    return R;
}

int main()
{
    ll n;
    citire(n);
    init();
    Matrice R=Exponentiere(n);
    g<<R.elem[2][1];


    return 0;
}