#include <bits/stdc++.h>

using namespace std;

vector<vector<long long>> inmultire(vector<vector<long long>> a, vector<vector<long long>> b) {

    int m = a.size();
    int n = a[0].size();
    int p = b[0].size();
    vector<vector<long long>> res{{0,0}, {0,0}};

    for (int k = 0; k < m; k++)
        for (int i = 0; i < p; i++)
            for (int j = 0; j < n; j++)
                res[k][i] += a[k][j] * b[j][i];
    return res;
}

vector<vector<long long>> mat_mod(vector<vector<long long>> a) {
    for (int i = 0; i < a.size(); i++)
        for (int j = 0; j < a[0].size(); j++)
            a[i][j] %= 666013;

    return a;
}

vector<vector<long long>> mat_putere(vector<vector<long long>> a, int k) {
    if (k == 0) return {{1, 0}, {0, 1}};
    if (k % 2 == 0) return mat_mod(mat_putere(mat_mod(inmultire(a, a)), k / 2));
    return mat_mod(inmultire(a, mat_mod(mat_putere(mat_mod(inmultire(a, a)), k / 2))));
}
int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");

    int k;
    fin >> k;

    vector<vector<long long>> a{{0, 1}, {1, 1}};
    vector<vector<long long>> res = mat_putere(a, k - 1);

    fout << (res[0][0] + res[1][0]) % 666013 << '\n';
    return 0;
}