#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;

int Z[2][2], ans[2][2];
int n;

inline void multiply(int a[][2], int b[][2], int c[][2]) {
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            for (int k = 0; k < 2; ++k)
                c[i][j] = ((c[i][j] % MOD) + ((1LL * (a[i][k] % MOD) * (b[k][j] % MOD)) % MOD)) % MOD;
}

inline void power(int mat[][2], int p) {
    mat[0][0] = mat[1][1] = 1;
    int aux[2][2];
    for (int i = 0; (1 << i) <= p; ++i) {
        if (p & (1 << i)) {
            memset(aux, 0, sizeof aux);
            multiply(ans, Z, aux);
            memcpy(ans, aux, sizeof aux);
        }
        memset(aux, 0, sizeof aux);
        multiply(Z, Z, aux);
        memcpy(Z, aux, sizeof aux);
    }
}

int main()
{
    fin >> n;
    Z[0][0] = 0;
    Z[0][1] = 1;
    Z[1][1] = 1;
    Z[1][0] = 1;
    power(ans, n - 1);
    fout << ans[1][1];
    return 0;
}