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

#define MOD 666013

typedef struct{
    uint64_t a,b,c,d;
}matrix;

matrix multiply_and_modulo(matrix A,matrix B)
{
    matrix R;
    R.a=(A.a*B.a+A.b*B.c)%MOD;
    R.b=(A.a*B.b+A.b*B.d)%MOD;
    R.c=(A.c*B.a+A.d*B.c)%MOD;
    R.d=(A.c*B.b+A.d*B.d)%MOD;
    return R;
}
matrix power(matrix base,uint64_t exp)//exp rpd
{
    matrix res={1,0,0,1};//I2
    while(exp>0)
    {
        if(exp%2)
        {
            res=multiply_and_modulo(res,base);
        }
        base=multiply_and_modulo(base,base);
        exp/=2;
    }
    return res;
}

int main(void)
{
    FILE *fin=fopen("kfib.in","r");
    FILE *fout=fopen("kfib.out","w");
    if(fin==NULL || fout==NULL)
    {
        fprintf(stderr,"eroare la deschiderea fisierelor");
        exit(EXIT_FAILURE);
    }
    uint64_t k;
    if((fscanf(fin,"%lu",&k))!=1)
    {
        fprintf(stderr,"eroare la citirea din fisier");
        exit(EXIT_FAILURE);
    }
    if(k==0)
    {
        fprintf(fout,"0\n");
    }
    else
    {
        matrix m={0,1,1,1};
        matrix mk=power(m,k-1);
        fprintf(fout,"%lu\n",mk.d);
    }
   
    if((fclose(fin))!=0)
    {
        fprintf(stderr,"eroare la inchiderea fisierului de citire");
        exit(EXIT_FAILURE);
    }
    if((fclose(fout))!=0)
    {
        fprintf(stderr,"eroare la inchiderea fisierului de scriere");
        exit(EXIT_FAILURE);
    }
    return 0;
}