#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;
long long a[2][2],ans[2][2],aux[2][2];

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int n;
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    fin >> n;
    n--;
    ans[0][0] = 1;
    ans[1][1] = 1;
    while (n) {
        if ((n & 1)) {
            for (int i = 0;i < 2;i++)
                for (int j = 0;j < 2;j++)
                    aux[i][j] = ans[i][0] * a[0][j] + ans[i][1] * a[1][j];
            for (int i = 0;i < 2;i++)
                for (int j = 0;j < 2;j++)
                    ans[i][j] = aux[i][j] % MOD;
        }
        for (int i = 0;i < 2;i++)
            for (int j = 0;j < 2;j++)
                aux[i][j] = a[i][0] * a[0][j] + a[i][1] * a[1][j];
        for (int i = 0;i < 2;i++)
            for (int j = 0;j < 2;j++)
                a[i][j] = aux[i][j] % MOD;
        n >>= 1;
    }
    fout << ans[1][1] << " ";
    return 0;
}