#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

const int MOD = 666013;

inline vector <vector <int>> mult(vector <vector <int>> &a, vector <vector <int>> &b) {
    int x = (int)a.size() - 1, y = (int)a[1].size() - 1, z = (int) b[1].size() - 1;
    vector <vector <int>> c(x + 1, vector <int>(z + 1));
    for(int i = 1; i <= x; i++) {
        for(int j = 1; j <= z; j++) {
            for(int k = 1; k <= y; k++) {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    if(n == 0 || n == 1) {
        cout << n;
        return 0;
    }

    vector <vector <int>> ans(3, vector <int>(3));
    vector <vector <int>> a(3, vector <int>(3));
    a[1][2] = a[2][1] = a[2][2] = 1;
    for(i = 1; i <= 2; i++) {
        ans[i][i] = 1;
    }
    n--;
    while(n > 0) {
        if(n & 1) ans = mult(ans, a);
        n >>= 1;
        a = mult(a, a);
    }
    cout << ans[2][2];

    return 0;
}