#include <bits/stdc++.h>

using namespace std;

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

#define int long long

int* mult(int* a, int* b)
{
    int* ret = new int[4];
    for(int i = 0; i < 2; i++)
    for(int j = 0; j < 2; j++)
        ret[i+i+j] = 0;

    for(int k = 0; k < 2; k++)
    for(int l = 0; l < 2; l++)
    for(int m = 0; m < 2; m++)
    {
        ret[k+k+l] += a[k+k+m] * b[m+m+l];
        ret[k+k+l] %= 666013;
    }

    return ret;
}

int* lgput(int* base, int exp)
{
    int* ret = new int[4];
    ret[0] = 1;
    ret[3] = 1;
    ret[1] = 0;
    ret[2] = 0;

    while(exp)
    {
        if(exp&1) ret = mult(ret, base);

        base = mult(base, base); exp /= 2;
    }

    return ret;
}

int32_t main()
{
    int k; in >> k;
    int* rez = new int[4];

    rez[0] = 0;
    rez[1] = 1;
    rez[2] = 1;
    rez[3] = 1;

    rez = lgput(rez, k);

    out << rez[2] << endl;
}