#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define mod 666013

typedef struct{
    uint64_t T11,T12,T21,T22;//un element pentru fiecare pozitie din matricea de 2x2
} mat_Z;

mat_Z inmultire(mat_Z A, mat_Z B)
{
    mat_Z produs;
    produs.T11=(A.T11*B.T11+A.T12*B.T21)%mod;//inmultirea pentru fiecare element dintr-un 2x2 inmultit cu alt 2x2 la care aplicam si modulo-ul ca sa nu ajungem la numere mai mari decat e necesar
    produs.T12=(A.T11*B.T12+A.T12*B.T22)%mod;
    produs.T21=(A.T21*B.T11+A.T22*B.T21)%mod;
    produs.T22=(A.T21*B.T12+A.T22*B.T22)%mod;
    return produs;
}

mat_Z ridicare(mat_Z baza, uint64_t putere) 
{
    mat_Z rezultat={1,0,0,1};//matricea identitate
    while(putere>0) 
    {
        if((putere%2)==1) 
        {
            rezultat=inmultire(rezultat,baza);
        }
        baza=inmultire(baza,baza);
        putere=putere/2;
    }
    return rezultat;
}

int main(void) 
{
    uint64_t k;
     
    FILE *fin=fopen("kfib.in", "r");//deschidem cele 2 fisiere
    FILE *fout=fopen("kfib.out", "w");

    if(fin==NULL)//verificam deschiderile celor 2 fisiere
    {
        perror("Eroare la deschiderea fisierului de citire.\n");
        exit(1);
    }
    if(fout==NULL)
    {
        perror("Eroare la deschiderea fisierului de scriere.\n");
        exit(1);
    }
   
    if(fscanf(fin,"%lu",&k)!=1)
    {
        perror("Eroare la citirea din fisier.\n");
        exit(1);
    }

    if(k==0) 
    {
        fprintf(fout, "0\n");//daca e vorba de al 0-lea termen, scriem 0 in fisier si am terminat
    }
    else 
    {
        mat_Z Z={0,1,1,1};//matricea cu care tot inmultim
        mat_Z final=ridicare(Z,k-1);
        fprintf(fout,"%lu\n",final.T22);//scriem in fisier doar termenul cerut
    }

    if(fclose(fin)!=0)//verificam si inchiderile
    {
        perror("Eroare la inchiderea fisierului de citire.\n");
        exit(1);
    }

    if(fclose(fout)!=0)
    {
        perror("Eroare la inchiderea fisierului de scriere.\n");
        exit(1);
    }

    return 0;
}