#include <iostream>
#include <fstream>
# define mod 666013
using namespace std;

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

struct fib
{
    long long x,nr,cop;
} m[5][5];

unsigned long long nr1 , i , j , a , b;

void f1()
{
    for(i = 1; i <= 2; ++i)
        for(j = 1; j <= 2; ++j)
            m[i][j].cop = m[i][j].x;

    for(i = 1; i <= 2; ++i)
        for(j = 1; j <= 2; ++j)
        {
            nr1 = 0;
            for(b = 1; b <= 2; ++b)
                nr1 +=((m[i][b].cop * m[b][j].cop)%mod);
                nr1%=mod;
            m[i][j].x = nr1;
        }
}

void f2()
{
    for(i = 1; i <= 2; ++i)
        for(j = 1; j <= 2; ++j)
        {
            nr1 = 0;
            for(b = 1; b <= 2; ++b)
                nr1 += ((m[i][b].x * m[b][j].nr)%mod);
            nr1 %= mod;
            m[i][j].cop = nr1;
        }
    for(i = 1; i <= 2; ++i)
        for(j = 1; j <= 2; ++j)
            m[i][j].nr = m[i][j].cop;
}

int main()
{
    f >> a;
    m[1][2].x = m[1][2].nr = 1;
    m[2][2].x = m[2][2].nr = 1;
    m[2][1].x = m[2][1].nr = 1;
    while(a)
    {
        if(a%2==1)
        {
            f2();
            --a;
        }
        else
        {
            f1();
            a /= 2 ;
        }
    }
    g << m[1][1].nr;
    return 0;
}