#include <bits/stdc++.h>
#define NMAX 505
#define INF LLONG_MAX
#define MOD 666013
#define vvi vector<vector<int>>

using namespace std;

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

int n;

vvi multiply(vvi m1, vector<vector<int>> m2) {
    int n = m1.size() - 1;
    int m = m1[0].size() - 1;
    int p = m2[0].size() - 1;
    vector<vector<int>> res(n + 1, vector<int>(p + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= m; k++) {
            for (int j = 1; j <= p; j++) {
                
                int to_add = 1ll * m1[i][k] * m2[k][j]  % MOD;
                res[i][j] = (res[i][j] + to_add) % MOD;
            }
        }
    }

    return res;
}

vvi ident = {{0, 0, 0}, {0, 1, 0}, {0, 0, 1}};

vvi log_pow(vvi m, int k) {
    if (k == 0) return ident;

    if (k % 2 == 0) {
        return log_pow(multiply(m, m), k / 2);
    } else {
        return multiply(m, log_pow(multiply(m, m), k / 2));
    }
}


int main() {
    f >> n;

    vvi fib1 = {{0, 0, 0}, {0, 1, 1}};
    vvi m = {{0, 0, 0}, {0, 1, 1}, {0, 1, 0}};

    m = log_pow(m, n - 2);
    m = multiply(fib1, m);

    g << m[1][1];
    return 0;
}