#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 666013;
int n, m[3][3], sol[3][3];

void Citire() {
    ifstream in("kfib.in");
    in >> n;
    in.close();
}

void InitializareMatrice() {
    m[0][0] = 0;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 1;
}

void Inmultire(int a[][3], int b[][3], int c[][3]) {
    for (int i = 0; i <= 1; ++i)
        for (int j = 0; j <= 1; ++j)
            for (int k = 0; k <= 1; ++k)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
}

void RidP(int p, int matrice[][3]) {
    int c[3][3], aux[3][3];
    memcpy(c, m, sizeof(m));
    matrice[0][0] = matrice[1][1] = 1;
    for (int i = 0; (1 << i) <= p; ++i) {
        if(p & (1 << i)) {
            memset(aux, 0, sizeof(aux));
            Inmultire(matrice, c, aux);
            memcpy(matrice, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        Inmultire(c, c, aux);
        memcpy(c, aux, sizeof(c));
    }
}

void Solve() {
    InitializareMatrice();
    RidP(n - 1, sol);
}

void Afisare() {
    ofstream out("kfib.out");
    out << sol[1][1] << '\n';
    out.close();
}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}