#include <fstream>
using namespace std;
const int MOD = 666013;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
void inmultire(long long A[2][2], long long B[2][2]) {
    long long temp[2][2];

    temp[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    temp[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    temp[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    temp[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            A[i][j] = temp[i][j];
        }
    }
}

void putere(long long mat[2][2], long long n) {
    long long rez[2][2] = { {1, 0}, {0, 1} };
    long long p[2][2];

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            p[i][j] = mat[i][j];
        }
    }

    while (n > 0) {
        if (n & 1) {
            inmultire(rez, p);
        }
        inmultire(p, p);
        n >>= 1;
    }

    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            mat[i][j] = rez[i][j];
        }
    }
}

int main() {
    long long k;
    fin >> k;
    long long fib[2][2] = { {1, 1}, {1, 0} };
    if (k == 0) {
        fout << 0 << '\n';
    }
    else {
        putere(fib, k - 1);
        fout << fib[0][0] << '\n';
    }
    return 0;
}