#include <iostream>
#include <fstream>

using namespace std;

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

const int mod = 666013;

int a[2][2] = {{0, 1}, {1, 1}};
int r[2][2] = {{0, 1}, {1, 1}};
int b[2][2];

int k;

int main()
{
    fin >> k;

    for(int i = 1; i < k; i++){
        for(int j = 0; j <= 1; j++)
            for(int k = 0; k <= 1; k++)
                b[j][k] = r[j][k];

        r[0][0] = (1LL * a[0][0] * b[0][0]) % mod + (1LL * a[0][1] * b[1][0]) % mod;
        r[0][1] = (1LL * a[0][0] * b[0][1]) % mod + (1LL * a[0][1] * b[1][1]) % mod;
        r[1][0] = (1LL * a[1][0] * b[0][0]) % mod + (1LL * a[1][1] * b[1][0]) % mod;
        r[1][1] = (1LL * a[1][0] * b[0][1]) % mod + (1LL * a[1][1] * b[1][1]) % mod;
    }

    fout << r[0][1];

    return 0;
}