#include <iostream>
#include <fstream>
#include <vector>

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

const int mod = 666013;
long long n, m[5][5], sol[5][5];

void Inmultire(long long a[5][5], long long b[5][5])
{
    long long aux[5][5];
    aux[1][1] = aux[0][0] = aux[0][1] = aux[1][0] = 0;
    for(int i = 0; i <= 1; i++)
    {
        for(int j = 0; j <= 1; j++)
        {
            for(int k = 0; k <= 1; k++)
            {
                aux[i][j] = (aux[i][j] + a[i][k]*b[k][j]*1LL)%mod;
            }
        }
    }
    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            a[i][j] = aux[i][j];
}

void putere(int p)
{
    while(p)
    {
        if(p%2 == 1) Inmultire(sol,m);
        Inmultire(m,m);
        p = p/2;
    }
}

int main()
{
    f>>n;
    m[0][0] = 0;
    m[1][0] = m[0][1] = m[1][1] = 1;
    sol[0][0] = sol[1][1] = 1;
    sol[1][0] = sol[0][1] = 0;
    putere(n-1);
    g<<sol[1][1]<<'\n';
    return 0;
}