#include <iostream>
#include <fstream>

using namespace std;

#define MOD 666013

long long fib01[2][1] = {{0}, {1}};
long long result[2];

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

long long z[2][2] = {
    {0, 1},
    {1, 1}
};

long long intermediary_matrix[2][2] = {
    {0, 1},
    {1, 1}
};

long long final_matrix[2][2];

int main() {
    int n;
    ifstream read("kfib.in");
    ofstream write("kfib.out");

    read >> n;

    if (n == 0) {
        write << 0 << endl;
        return 0;
    } else if (n == 1) {
        write << 1 << endl;
        return 0;
    }

    for (int i = 1; i < n; i++) {
        multiply_2_by_2_matrices(z, intermediary_matrix, final_matrix);
        for (int i1 = 0; i1 < 2; i1++) {
            for (int i2 = 0; i2 < 2; i2++) {
                intermediary_matrix[i1][i2] = final_matrix[i1][i2];
            }
        }
    }

    result[0] = (fib01[0][0] * final_matrix[0][0] + fib01[1][0] * final_matrix[1][0]) % MOD;

    write << result[0] << endl;
    return 0;
}