#include <fstream>
#include <vector>

std::ifstream fin("kfib.in");
std::ofstream fout("kfib.out");

typedef long long ll;
ll const MOD = 666013;

struct Matrix {
    std::vector<std::vector<ll>> mat;
    int n, m;

    Matrix (int _n, int _m) {
        n = _n, m = _m;
        mat.resize(n);
        for (int i = 0; i < n; i++)
            mat[i].resize(m);
    }

    Matrix operator * (Matrix other) {
        Matrix result(n, m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < n; k++)
                    result.mat[i][j] = (result.mat[i][j] +
                            (mat[i][k] * other.mat[k][j]) % MOD) % MOD;
        return result;
    }
};

Matrix logPow(Matrix a, int b) {
    Matrix ans(a.n, a.m);
    ans.mat[0][0] = ans.mat[1][1] = 1;
    while (b) {
        if (b & 1)
            ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

int main() {
    int k;
    fin >> k;
    Matrix companion(2, 2);
    companion.mat[0][0] = 0;
    companion.mat[0][1] = 1;
    companion.mat[1][0] = 1;
    companion.mat[1][1] = 1;
    Matrix ans = logPow(companion, k);
    Matrix fib(2, 2);
    fib.mat[0][0] = 0;
    fib.mat[1][0] = 1;
    ans = ans * fib;
    fout << ans.mat[0][0] << "\n";
    return 0;
}