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

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

const int MOD = 666013;

struct Matrix {
    int mat[2][2] = {};
    inline int* operator[](int ind) {
        return mat[ind];
    }
} mat, one;

Matrix operator*(Matrix a, Matrix b) {
    Matrix p;
    p[0][0] = (1LL * a[0][0] * b[0][0] + 1LL * a[0][1] * b[1][0]) % MOD;
    p[0][1] = (1LL * a[0][0] * b[0][1] + 1LL * a[0][1] * b[1][1]) % MOD;
    p[1][0] = (1LL * a[1][0] * b[0][0] + 1LL * a[1][1] * b[1][0]) % MOD;
    p[1][1] = (1LL * a[1][0] * b[0][1] + 1LL * a[1][1] * b[1][1]) % MOD;
    return p;
}

Matrix pwr(Matrix x, int n) {
    if (!n)
        return one;
    if (n & 1)
        return x * pwr(x * x, n >> 1);
    return pwr(x * x, n >> 1);
}

int main() {
    mat[0][0] = 1; mat[0][1] = 1;
    mat[1][0] = 1; mat[1][1] = 0;

    one[0][0] = 1; one[0][1] = 0;
    one[1][0] = 0; one[1][1] = 1;

    int n; fin >> n;
    fout << pwr(mat, n)[0][1] << '\n';

    fout.close();
    return 0;
}