#include <fstream>
#include <vector>

using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

int n;
vector<vector<int>> a(2, vector<int>(2, 0)), b(2, vector<int>(2, 1));
const int MOD = 666013;

void mul(vector<vector<int>> &x, vector<vector<int>> &y) {
    vector<vector<int>> z(2, vector<int>(2, 0));
    for (int k = 0 ; k < 2 ; ++k) {
        for (int j = 0 ; j < 2 ; ++j) {
            for (int i = 0 ; i < 2 ; ++i) {
                z[k][j] = (z[k][j] + ((1LL * x[k][i] * y[i][j]) % MOD)) % MOD;
            }
        }
    }
    x = z;
}

void exp(int power) {
    while (power) {
        if (power % 2) mul(a, b);
        mul(b, b);
        power /= 2;
    }
}

int main() {
    cin >> n;
    b[0][0] = 0;
    a[0][0] = a[0][1] = 1;
    exp(n - 1);
    cout << a[0][0];
}