#include <iostream>
#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int m[2][2], rasp[2][2], n;

//Functie care inmulteste matricea a cu b, punand rezultatul in a
void inmultireMatrice(int a[][2], int b[][2]) {
    int aa[2][2]; //Copie a lui a
    aa[0][0] = a[0][0]; aa[0][1] = a[0][1];
    aa[1][0] = a[1][0]; aa[1][1] = a[1][1];

    int bb[2][2]; //Copie a lui b
    bb[0][0] = b[0][0]; bb[0][1] = b[0][1];
    bb[1][0] = b[1][0]; bb[1][1] = b[1][1];

    a[0][0] = ((long long)aa[0][0] * bb[0][0] + aa[0][1] * bb[1][0]) % 666013;
    a[0][1] = ((long long)aa[0][0] * bb[0][1] + aa[0][1] * bb[1][1]) % 666013;
    a[1][0] = ((long long)aa[1][0] * bb[0][0] + aa[1][1] * bb[1][0]) % 666013;
    a[1][1] = ((long long)aa[1][0] * bb[0][1] + aa[1][1] * bb[1][1]) % 666013;
}

void ridicare(int n) {
    while(n > 0) {
        if(n % 2 == 1)
            inmultireMatrice(rasp, m);
        inmultireMatrice(m, m);
        n /= 2;
    }
}

int main()
{
    //Citim n
    in >> n;

    //Matricea initiala
    m[0][0] = 1; m[0][1] = 1;
    m[1][0] = 1; m[1][1] = 0;

    //Matricea raspuns (initial este egala cu I2)
    rasp[0][0] = 1; rasp[0][1] = 0;
    rasp[1][0] = 0; rasp[1][1] = 1;

    //Ridicam matricea la puterea n
    ridicare(n);

    //Afisam cel de-al n-lea termen Fibonacci
    cout << rasp[0][1];
    return 0;
}