#include <fstream>
using namespace std;

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

const int MOD = 666013;

void inmultire(long long m1[][5], long long m2[][5]) {
    long long a = m1[0][0], b = m1[0][1], c = m1[1][0], d = m1[1][1];
    long long e = m2[0][0], f = m2[0][1], g = m2[1][0], h = m2[1][1];

    m1[0][0] = (a * e + b * g) % MOD;
    m1[0][1] = (a * f + b * h) % MOD;
    m1[1][0] = (c * e + d * g) % MOD;
    m1[1][1] = (c * f + d * h) % MOD;
}

int main() {
    int n;
    fin >> n;

    long long m[5][5];
    m[0][0] = m[0][1] = m[1][0] = 1;
    m[1][1] = 0;

    long long f[5][5];
    f[0][0] = f[1][1] = 1;
    f[0][1] = f[1][0] = 0;

    while (n) {
        if (n % 2) {
            inmultire(f, m);
        }
        inmultire(m, m);

        n /= 2;
    }

    fout << f[0][1];
    return 0;
}