#include <iostream>
#include <fstream>
#include <cstring>

#define mod 666013

using namespace std;

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

int k;
long long a[2][2], sol[2][2];

void init()
{
    a[0][0]=0;
    a[0][1]=a[1][0]=a[1][1]=1;
}

void inmultire(long long a[][2], long long b[][2], long long c[][2])
{
    for(int i=0; i<2; ++i)
    {
        for(int j=0; j<2; ++j)
        {
            for(int k=0; k<2; ++k)
            {
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
}

void Search()
{
    long long aux[2][2];
    sol[0][0]=sol[1][1]=1;
    for(int i=0; (1<<i)<k; ++i)
    {
        if((1<<i)&(k-1))
        {
            memset(aux, 0, sizeof(aux));
            inmultire(sol, a, aux);
            memcpy(sol, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        inmultire(a, a, aux);
        memcpy(a, aux, sizeof(aux));
    }
    g<<sol[1][1];
}

int main()
{
    f>>k;
    init();
    Search();
    return 0;
}