#include <bits/stdc++.h>
//#define int long long
#define ll pair<long long, long long>
using namespace std;
int const mod = 666013;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

vector<vector<int>> find_product(vector<vector<int>> m1, vector<vector<int>> m2) {
    int rows1 = m1.size(), cols1 = m1[0].size(), cols2 = m2[0].size();
    vector<vector<int>> ans(rows1, vector<int>(cols2));
    for (int i = 0; i < rows1; ++i) {
        for (int j = 0; j < cols2; ++j) {
            for (int k = 0; k < cols1; ++k) {
                ans[i][j] = 1LL * ans[i][j] + 1LL * m1[i][k] * m2[k][j] % mod;
                ans[i][j] %= mod;
            }
        }
    }
    return ans;
}

vector<vector<int>> fast_expo(vector<vector<int>> m1, int pw) {
    if (pw == 1) {
        return m1;
    }
    vector<vector<int>> ans = find_product(fast_expo(m1, pw / 2), fast_expo(m1, pw / 2));
    if (pw & 1) {
        ans = find_product(ans, m1);
    }
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        int n;
        fin >> n;
        vector<vector<int>> m(2, vector<int>(2)), basecase(2, vector<int>(1));
        m[0][0] = m[0][1] = m[1][0] = 1;
        basecase[0][0] = 1;
        vector<vector<int>> ans = find_product(fast_expo(m, n - 1), basecase);
        fout << ans[0][0];
    }
    return 0;
}