#include <fstream>

using namespace std;

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

const int MOD = 666013;
int n;

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

void cpy(long long a[2][2], long long b[2][2]) {
    for (int i = 0; i <= 1; i++)
        for (int j = 0; j <= 1; j++)
            a[i][j] = b[i][j];
}

int main() {
    fin >> n;
    if (n <= 2) {
        fout << 1;
        return 0;
    }
    n -= 2;

    long long a[2][2] = { { 1, 1 },
                          { 1, 0 } };
    long long p[2][2] = { { 1, 0 },
                          { 0, 1 }};
    long long aux[2][2];
    while (n != 0) {
        if (n % 2 != 0) {
            mult(p, a, aux);
            cpy(p, aux);
        }

        mult(a, a, aux);
        cpy(a, aux);
        n /= 2;
    }

    fout << (p[0][0] + p[0][1]) % MOD;

    return 0;
}