#include <iostream>
#include <fstream>

using namespace std;

const int MOD = 666013;

struct Matrice {
    long long mat[2][2];
};

Matrice inmultire(Matrice A, Matrice B) {
    Matrice C;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            C.mat[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

Matrice ridicare_la_putere(Matrice baza, long long exponent) {
    Matrice rez = { {{1, 0}, {0, 1}} };// e matrice a I(2)

    while (exponent > 0) {
        if (exponent & 1) {
            rez = inmultire(rez, baza);
        }
        baza = inmultire(baza, baza);
        exponent >>= 1; // echivalent cu impartire la 2---> timp logaritmic de inmultire pt matrici 
    }
    return rez;
}

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

    long long K;
    if (!(fin >> K)) return 0;

    if (K == 0) {
        fout << 0 << "\n";
        return 0;
    }
    if (K == 1) {
        fout << 1 << "\n";
        return 0;
    }

    
    Matrice Z = { {{0, 1}, {1, 1}} };


    Matrice Z_putere = ridicare_la_putere(Z, K - 1);

    long long FK = Z_putere.mat[1][1];

    fout << FK << "\n";

    return 0;
}