// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MOD = 666013;

vector<vector<int>> inmultire(vector<vector<int>> a, vector<vector<int>> b) {
    vector<vector<int>> c(3, vector<int>(3));
    for(int i = 1; i <= 2; i++) {
        for(int j = 1; j <= 2; j++) {
            c[i][j] = 0;
            for(int k = 1; k <= 2; k++) {
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= MOD;
            }
        }
    }
    return c;
}

vector<vector<int>> expo(vector<vector<int>> a, int n) {
    if(n == 0) {
        vector<vector<int>> I(3, vector<int>(3));
        I[1][1] = I[2][2] = 1;
        I[1][2] = I[2][1] = 0;
        return I;
    } else {
        vector<vector<int>> p = expo(a, n / 2);
        if(n % 2 == 0) {
            return inmultire(p, p);
        } else {
            return inmultire(inmultire(p, p), a);
        }
    }
}

signed main() {
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    int k;
    cin >> k;
	vector<vector<int>> F(3, vector<int>(3));
    F[1][1] = F[1][2] = 1;
    F[2][1] = F[2][2] = 0;

    vector<vector<int>> A(3, vector<int>(3));
    A[1][1] = 0;
    A[1][2] = A[2][1] = A[2][2] = 1;

    vector<vector<int>> res = inmultire(F, expo(A, k - 2));
    cout << res[1][2];
}