#include <iostream>
#include <fstream>
#include <utility>

#define MOD 666013
#define tip long long
#define matrix pair<pair<tip,tip>,pair<tip,tip> >
#define m11 first.first
#define m12 first.second
#define m21 second.first
#define m22 second.second

using namespace std;

matrix a,b;
matrix operator*(matrix a, matrix b);

int main()
{
    tip k;
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    a.m11 = 0; a.m12 = 1;
    a.m21 = 1; a.m22 = 1;
    b.m11 = 1; b.m12 = 0;
    b.m21 = 0; b.m22 = 1;
    f>>k;
    for(;k;k>>=1)
    {
        if(k&1)b=b*a;
        a=a*a;
    }
    g<<b.m12;
    return 0;
}

matrix operator*(matrix a, matrix b)
{
    matrix x;
    x.m11 = (a.m11*b.m11 + a.m12*b.m21)%MOD;
    x.m12 = (a.m11*b.m12 + a.m12*b.m22)%MOD;
    x.m21 = (a.m21*b.m11 + a.m22*b.m21)%MOD;
    x.m22 = (a.m21*b.m12 + a.m22*b.m22)%MOD;
    return x;
}