#include <fstream>

using namespace std;

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

const int mod = 666013;
int k, v[5][5], m[5][5];

void inm(int a[5][5], int b[5][5])
{
    int sol[5][5];
    sol[1][1] = ((1LL * a[1][1] * b[1][1]) % mod + (1LL * a[1][2] * b[2][1]) % mod) % mod;
    sol[1][2] = ((1LL * a[1][1] * b[1][2]) % mod + (1LL * a[1][2] * b[2][2]) % mod) % mod;
    sol[2][1] = ((1LL * a[2][1] * b[1][1]) % mod + (1LL * a[2][2] * b[2][1]) % mod) % mod;
    sol[2][2] = ((1LL * a[2][1] * b[1][2]) % mod + (1LL * a[2][2] * b[2][2]) % mod) % mod;

    a[1][1] = sol[1][1]; a[1][2] = sol[1][2];
    a[2][1] = sol[2][1]; a[2][2] = sol[2][2];
}

int main()
{
    f >> k;

    if(k == 0){
        g << 0;
        return 0;
    }

    m[1][2] = m[2][1] = m[2][2] = 1;
    v[1][1] = v[2][2] = 1;

    k --;
    while(k)
    {
        if(k % 2 == 0){
            inm(m, m);
            k /= 2;
        }

        else{
            inm(v, m);
            k --;
        }
    }

    g << v[2][2];
    return 0;
}