#include <iostream>
#include <cstdio>
#include <vector>
typedef long long ll;

const int MOD = 666013;

//typedef std::vector<int> vi;
//typedef std::vector<std::vector<int>> vvi;
typedef std::vector<ll> vll;
typedef std::vector<std::vector<ll>> vvll;

vvll matrixMultiplication(int n, vvll a, vvll b) {
    vvll c;
    c.resize(n, vll(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++)
                c[i][j] += (a[i][k] * b[k][j]);
            c[i][j] %= MOD;
        }
    return c;
}

vvll fibo = {
        {1, 1},
        {1, 0}
};

int rise(vvll base, int exp) {
    vvll res = {
            {1, 0},
            {0, 1}
    };
    while (exp) {
        if (exp & 1)
            res = matrixMultiplication(2, res, base);
        base = matrixMultiplication(2, base, base);
        exp >>= 1;
    }
    return res[0][0];
}

int main() {
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::cout << rise(fibo, n - 1);
    return 0;
}