#include <fstream>

// 0 1 2 3 4 5 6 7  8
// 0 1 1 2 3 5 8 13 21

using namespace std;

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

typedef long long int MAT[3][3];
int math1[3][3], math2[3][3], m1[3][3], resturi[3][3][1000];
int rst;

void update (int save[][3]) {
    math1[1][1] = math2[1][1] = save[1][1];
    math1[1][2] = math2[1][2] = save[1][2];
    math1[2][1] = math2[2][1] = save[2][1];
    math1[2][2] = math2[2][2] = save[2][2];
}

void addRest (int save[][3]) {
    resturi[1][1][++rst] = save[1][1];
    resturi[1][2][rst] = save[1][2];
    resturi[2][1][rst] = save[2][1];
    resturi[2][2][rst] = save[2][2];
}

void square () {
    int aux[3][3];
    aux[1][1] = (math1[1][1] * math2[1][1] % 666013 + math1[1][2] * math2[2][1] % 666013) % 666013;
    aux[1][2] = (math1[1][1] * math2[1][2] % 666013 + math1[1][2] * math2[2][2] % 666013) % 666013;
    aux[2][1] = (math1[2][1] * math2[1][1] % 666013 + math1[2][2] * math2[2][1] % 666013) % 666013;
    aux[2][2] = (math1[2][1] * math2[1][2] % 666013 + math1[2][2] * math2[2][2] % 666013) % 666013;
    update(aux);
    return;
}

void multiply (int matrice1[][3], int matrice2[][3]) {
    int aux[3][3];
    aux[1][1] = (matrice1[1][1] * matrice2[1][1] % 666013 + matrice1[1][2] * matrice2[2][1] % 666013) % 666013;
    aux[1][2] = (matrice1[1][1] * matrice2[1][2] % 666013 + matrice1[1][2] * matrice2[2][2] % 666013) % 666013;
    aux[2][1] = (matrice1[2][1] * matrice2[1][1] % 666013 + matrice1[2][2] * matrice2[2][1] % 666013) % 666013;
    aux[2][2] = (matrice1[2][1] * matrice2[1][2] % 666013 + matrice1[2][2] * matrice2[2][2] % 666013) % 666013;
    update(aux);
    return;
}

void putLog (int n) {
    if (n == 1) return;
    else if (n % 2 == 0) {
        square();
        putLog(n/2);
    }
    else {
        addRest(math1);
        square();
        putLog((n-1)/2);
    }
}

int main()
{
    int n;

    math1[1][1] = 0;
    math1[1][2] = 1;
    math1[2][1] = 1;
    math1[2][2] = 1;

    update(math1);


    fin >> n;

    putLog(n);

    while (rst>0) {
        int aux[3][3];
        aux [1][1] = resturi[1][1][rst];
        aux [1][2] = resturi[1][2][rst];
        aux [2][1] = resturi[2][1][rst];
        aux [2][2] = resturi[2][2][rst];
        multiply(aux, math1);
        rst--;
    }

    fout << math1[1][2] % 666013;

    return 0;
}