/*problema vrea sa gaseasca al n-lea termen al lui Fibonacci modulo 666013 (restul acestui numar la 666013)
se poate face cu 3 variabile care comuta in O(n)
                                                                                                    0 1
o rezolvare mai rapida in O(logn) este cu ajutorul matricelor, mai precis cu ajutorul matricei      1 1  numita in continuare mat
Notam matricea cu o linie (fi-1, fi) cu Ai, unde fi al i-lea termen Fibonacci
Se observa ca (fn-2 fn-1) * mat = (fn-1 fn) si prin inductie gasim ca Ai=A1*pow(mat, i-1)
Deci totul se reduce la calculul lui pow(m, i-1), rezultat care se gaseste in timp logaritmic. Practic nu vom face mat*mat*...*mat de i-1 ori deoarece ar fi mai
ineficient decat metoda de pe randul 2 al commentului, ci vom calcula numai din pow(mat,8) in pow(mat,8) adica logn operatii
*/
#include <fstream>
#include <cstring> //pentru a putea folosi memcpy si memset
#define modulo 666013
using namespace std;

//realizez o functie care inmulteste doua matrice transmise ca parametri A si B si retine rezultatul in c
//cele doua matrice au 2 linii si 2 coloane, iar rezultatul va avea tot 2 linii si 2 coloane

void inmult(long long a[3][3], long long b[3][3], long long c[3][3])
{
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j])%modulo;
}

int main()
{
    //folosesc matricele c si aux pentru a realiza inmultirile, iar in m voi retine rezultatul.
    long long c[3][3], aux[3][3],m[3][3],mat[3][3];
    int i,n;
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin>>n;
    //initializez matricea mat cu     0 1 si o notez cu mat
    //                              1 1
    mat[0][0] = 0; mat[0][1] = 1; mat[1][0] = 1; mat[1][1] = 1;

    //copii continutul matricei mat in c
    memcpy(c, mat, sizeof(mat));
    //m porneste de la matricea I2, element neutru la inmultirea matricelor
    m[0][1]=0;
    m[0][0]=1;
    m[1][1]=1;
    m[1][0]=0;
    //relatia mea este pow(2, nrinmultiri)=n, de aici rezulta nrinmultiri =logn
    //1<<i este echivalent cu pow(2,i), dar este mult mai rapid
    //parcurg numai pana cand pow(2,i) ajunge la n-1

    for (i = 0; (1 << i) <= n-1; i++)
    {
        //daca bitul lui n-1 din dsc in baza 2 este cel corecp lui pow(2,i) atunci va trebui sa facem inmultirea m*mat
        if (((n-1) & (1 << i))!=0)
        {
            //mai intai initializez matrice aux cu 0
            memset(aux, 0, sizeof(aux));
            //inmultesc practic matricea unde am ajuns cu matricea mat retinuta acum de c si retin rezultatul in aux
            inmult(m, c, aux);
            //copii acum rezultatul in m, pentru a putea face corect urm inmultire de matrice
            memcpy(m, aux, sizeof(aux));
        }
        //la fiecare pas trebuie sa inmultesc cu mat*mat
        //resetez aux la 0
        memset(aux, 0, sizeof(aux));
        //inmultesc c*c si retin in aux
        inmult(c, c, aux);
        //copii aux in c
        memcpy(c, aux, sizeof(c));
    }
    //m va fi acum o matrice cu 2 linii, 2 coloane care retine pe [0][0] fibo n-1 si pe [1][1] fibo n
    fout<<m[1][1];
    return 0;
}