#include <fstream>
#define MOD 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

typedef unsigned long long ULL;

void multiply(int a[2][2], int b[2][2], int r[2][2]) {
    int aux[2][2];
    aux[0][0] = (1LL * a[0][0] * b[0][0] + 1LL * a[0][1] * b[1][0]) % MOD;
    aux[0][1] = (1LL * a[0][0] * b[0][1] + 1LL * a[0][1] * b[1][1]) % MOD;
    aux[1][0] = (1LL * a[1][0] * b[0][0] + 1LL * a[1][1] * b[1][0]) % MOD;
    aux[1][1] = (1LL * a[1][0] * b[0][1] + 1LL * a[1][1] * b[1][1]) % MOD;

    r[0][0] = aux[0][0], r[0][1] = aux[0][1], r[1][0] = aux[1][0], r[1][1] = aux[1][1];
}

void pow(int base[2][2], int exp, int r[2][2]) {
    while (exp) {
        if (exp & 1)
            multiply(r, base, r);
        multiply(base, base, base);
        exp >>= 1;
    }
}

// ! probabil se putea si fara inmultire de matrici pt ca nr fibonacci sunt periodice cu MOD
int main() {
    int p;
    f >> p;

    if (p == 0) {
        g << 0 << '\n';
        return 0;
    }
    int base[2][2] = {
        {0, 1},
        {1, 1}};

    int r[2][2] = {
        {1, 0},
        {0, 1}};

    pow(base, p - 1, r);
    g << r[1][1] << '\n';
    return 0;
}