#include <bits/stdc++.h>

using namespace std;

#define KMAX 2
#define MOD 666013
void multiply_matrix(long A[KMAX][KMAX], long B[KMAX][KMAX], long C[KMAX][KMAX]) {
    long tmp[KMAX][KMAX];

    for (int i = 0; i < KMAX; ++i) {
        for (int j = 0; j < KMAX; ++j) {
            long sum = 0;
            for (int k = 0; k < KMAX; ++k) {
                sum = (sum + 1LL * A[i][k] * B[k][j]) % MOD;
            }
            tmp[i][j] = sum;
        }
    }

    memcpy(C, tmp, sizeof(tmp));
}

void power_matrix(long C[KMAX][KMAX], long exp, long res[KMAX][KMAX]) {
    long tmp[KMAX][KMAX];
    for (int i = 0; i < KMAX; ++i)
        for (int j = 0; j < KMAX; ++j)
            tmp[i][j] = i == j ? 1 : 0;
    
    while (exp > 1) {
        if (exp & 1) {
            --exp;
            multiply_matrix(tmp, C, tmp);
        } else {
            multiply_matrix(C, C, C);
            exp >>= 1;
        }
    }
    multiply_matrix(tmp, C, res);
}

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

    int k;
    fin >> k;

    long fibo[KMAX][KMAX] = {{0, 1}, {1, 1}};

    power_matrix(fibo, k - 1, fibo);

    fout << fibo[1][1] << '\n';

    return 0;
}