#include <bits/stdc++.h>

#define MOD 666013

using namespace std;

int mod_multiply(int a, int b, int mod) {
    return 1ll * (1ll * (1ll * (a % mod) * 1ll * (b % mod))) % (1ll * mod);
}
 
void mult_mat(int A[2][2], int B[2][2], int C[2][2], int mod) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            C[i][j] = 0;
 
            for (int k = 0; k < 2; ++k) {
                C[i][j] += mod_multiply(A[i][k], B[k][j], mod);
            }
 
            C[i][j] %= mod;
        }
    }
}
 
void copy_mat(int dest[2][2], int src[2][2]) {
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            dest[i][j] = src[i][j];
        }
    }
}
 
void fast_pow(int base[2][2], int exponent, int mod, int result[2][2]) {
    if (exponent <= 0) {
        result[0][0] = result[1][1] = 1;
        return;
    }
 
    fast_pow(base, exponent / 2, mod, result);
 
    int res_aux[2][2] = {0};
    if (exponent % 2 == 0) {
        mult_mat(result, result, res_aux, mod);
    } else {
        mult_mat(result, result, res_aux, mod);
        copy_mat(result, res_aux);
 
        mult_mat(base, result, res_aux, mod);
    }
 
    copy_mat(result, res_aux);
}

int main(void) {
    freopen("kfib.in", "rt", stdin);
    freopen("kfib.out", "wt", stdout);

    int k;
    cin >> k;

    int mat[2][2] = {{1, 1}, {1, 0}};
    int res[2][2] = {0};
 
    fast_pow(mat, k - 1, MOD, res);
 
    cout << res[0][0] << "\n";

    return 0;
}