#include <iostream>
#include <fstream>
using namespace std;
const int MOD = 666013;

struct MAT
{
    long long a11, a12, a22;
};

MAT A = {1, 1, 0}, I = {1, 0, 1};

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

void multmat(MAT &A, MAT &B)
{
    long long x=A.a11*B.a11+A.a12*B.a12;
    long long y=A.a11*B.a12+A.a12*B.a22;
    long long z=A.a12*B.a12+A.a22*B.a22;
    A.a11=x%MOD;
    A.a12=y%MOD;
    A.a22=z%MOD;
}

void puteremat(int p)
{
    while(p)
    {
        if(p & 1)
            multmat(I, A);
        multmat(A, A);
        p >>= 1;
    }
}

int main()
{
    int k;
    f >> k;
    if(k)
    {
        puteremat(k - 1);
        g << I.a11;
    }
    else
        g << '0';
    f.close();
    g.close();
    return 0;
}