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

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

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(r, base, r);
        exp >>= 1;
    }
}

int main() {
    int p;
    f >> p;

    // if (p == 0) {
    //     g << 0 << endl;
    //     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] << endl;
    return 0;
}