#include <iostream>
#include <fstream>
#define N 5
#define ll long long
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

const ll MOD = 666013;
ll n;
ll c[2][2], sol[2][2], a[2][2];
void inm(ll a[2][2],ll b[2][2])
{
    ll c[2][2];
    int i,j,k;
    for(i=0; i<=1; i++)
    {
        for(j=0; j<=1; j++)
        {
            c[i][j]=0;
            for(k=0; k<=1; k++)
                c[i][j]+=a[i][k]*b[k][j];
            c[i][j]=c[i][j]%MOD;
        }
    }
    for(i=0; i<=1; i++)
        for(j=0; j<=1; j++)
            a[i][j]=c[i][j];
}
void put(ll a[2][2],ll k)
{
    while(k)
    {
        if(k%2)
            inm(a, c);
        k/=2;
        inm(c, c);
    }
}
int main()
{
    sol[0][0] = sol[1][1] = 1;
    a[0][0] = a[0][1] = 1;
    c[0][1] = c[1][0] = c[1][1] = 1;
    f>> n;
    n--;
    put(sol, n);
    inm(a, sol);
    g<< a[0][0];
    return 0;
}