#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013;

int k;

void multiply(long long A[2][2], long long B[2][2], long long result[2][2]) {
    result[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    result[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    result[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    result[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
}

void copy_matrix_from_src_to_dest(long long source[2][2], long long dest[2][2]) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            dest[i][j] = source[i][j];
        }
    }
}

void power(long long matrix[2][2], int n, long long result[2][2]) {
    result[0][0] = 1;
    result[0][1] = 0;
    result[1][0] = 0;
    result[1][1] = 1;

    for (; n > 0; n /= 2) {
        if (n % 2 == 1) {
            long long temp[2][2];
            multiply(result, matrix, temp);
            copy_matrix_from_src_to_dest(temp, result);
        }

        long long temp[2][2];
        multiply(matrix, matrix, temp);
        copy_matrix_from_src_to_dest(temp, matrix);
    }
}

int get_fibomod_result(int n) {
    if (n == 0) {
        return 0;
    }
    long long matrix[2][2] = {{1, 1}, {1, 0}};
    long long result[2][2];
    power(matrix, n - 1, result);
    return result[0][0];
}

int main() {
    f >> k;
    g << get_fibomod_result(k) << '\n';
    f.close();
    g.close();
}