/*
    Fibonacci cu for simplu are O(n). Daca imi convine, fac asta.

    Daca daca imi trebuie fibo[9999999999]? Pentru asta nu mai fac for.

    Fibonacci - O(MOD) - merge doar pentru termeni modulo MOD
        - presupun ca MOD <<<<< n (mult mai mic)

    presupun ca MOD = 5, calculam termenii modulo 5
    0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1
    Se observa ca s-a ajuns din nou la 0, 1 (secventa de inceput) =>
    ca sirul e periodic

    Daca p este lungimea perioadei =>
    fibo[i] = fibo[i+p] = ... = fibo[i+n*p]

*/
#include <fstream>
#include <vector>
#define MOD 666013

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

int n;
vector <int> fibo;

int main()
{
    f>>n;
    fibo.push_back(0);
    fibo.push_back(1);
    int i = 2;
    while (1) //  calculeaza inca un termen, pana s-a incheiat perioada
    {
        int current = (fibo[i-1]+fibo[i-2]) % MOD;
        fibo.push_back(current);
        if (fibo[i-1]==0 && fibo[i]==1) break; // am intrat in a doua perioada
        i++;
    }
    // momentan vectorul contine numerele 0,1 din a doua perioada. le sterg
    fibo.pop_back();
    fibo.pop_back();
    int p=fibo.size(); // lungimea perioadei

    int poz = n % p;
    //if (poz == 0) poz = p - 1;

    g<<fibo[poz]<<' ';
    f.close();
    g.close();
    return 0;
}


/*
    0  1  2  3  4  5  6  7  8  9  10
    0, 1, 1, 2, 3, 0, 1, 1, 2, 3, 0
    p  = 5

    n = 2 => n = n%p = 2 => rez = fibo[2] = 1
    n = 6 => n = n%p = 1 => rez = fibo[1] = 1
    n =

*/