#include <bits/stdc++.h>
#define mod 666013
#define ll long long
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
ll a,b;
void inmultire_matrici(ll n, ll p, ll m, ll A[5][5], ll B[5][5], ll C[5][5])
{
    for(ll i=1; i<=n; i++)
    {
        for(ll j=1; j<=m; j++)
        {
            C[i][j]=0;
            for(ll k=1; k<=p; k++)
            {
                C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod)%mod;
            }
        }
    }
}
void ridicare_la_putere_de_matrici_in_timp_logaritmic(ll putere, ll C[5][5], ll Matricea_de_inmultit[5][5], ll n)
{
    ll M[5][5];
    if(putere==1)
    {
        for(ll i=1; i<=n; i++)
        {
            for(ll j=1; j<=n; j++)
            {
                C[i][j]=Matricea_de_inmultit[i][j];
            }
        }
    }
    else
    {
        ridicare_la_putere_de_matrici_in_timp_logaritmic(putere/2,M,Matricea_de_inmultit,n);
        if(putere%2)
        {
            ll O[5][5];
            inmultire_matrici(n,n,n,M,M,O);
            inmultire_matrici(n,n,n,O,Matricea_de_inmultit,C);
        }
        else
        {
            inmultire_matrici(n,n,n,M,M,C);
        }
    }
}
int main()
{
    ll n,matrice[5][5],s[5][5];
    matrice[1][1]=1;
    matrice[1][2]=1;
    matrice[2][1]=1;
    matrice[2][2]=0;
    in >> n;
    if(n==1)
    {
        out << 1;
        return 0;
    }
    if(n==0)
    {
        out << 0;
        return 0;
    }
    ridicare_la_putere_de_matrici_in_timp_logaritmic(n-1,s,matrice,2);
    matrice[1][1]=1;
    matrice[1][2]=0;
    ll rez[5][5];
    inmultire_matrici(1,2,2,matrice,s,rez);
    out << rez[1][1];
    return 0;
}