#include <bits/stdc++.h>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
struct mat {
    int a[3][3];
    mat() {
        memset(a, 0, sizeof(a));
    }
};
const int mod = 666013;

mat prod(mat A, mat B) {
    mat ans;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                ans.a[i][j] = (ans.a[i][j] + 1LL * A.a[i][k] * B.a[k][j]) % mod;
    return ans;
}

mat lgp(mat A, int p) {
    mat ans;
    ans.a[0][0] = ans.a[1][1] = 1;

    while (p) {
        if (p & 1) {
            ans = prod(ans, A);
            p--;
        }

        p >>= 1;
        A = prod(A, A);
    }

    return ans;
}
int n;
mat M, sol;
int main()
{
    in>>n;
    sol.a[0][0] = 1;
    sol.a[0][1] = 1;

    M.a[0][1] = 1;
    M.a[1][0] = M.a[1][1] = 1;

    if (n <= 2) {
        out << 1;
    } else {
        M = lgp(M, n - 2);
        sol = prod(sol, M);
        out << sol.a[0][1];
    }
    return 0;
}