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

#define MOD 666013

typedef struct {
    long long a, b, c, d;
} Mat;

Mat inmultire(Mat x, Mat y)
{
    Mat r;
    r.a = (x.a*y.a)%MOD + (x.b*y.c)%MOD;
    r.b = (x.a*y.b)%MOD + (x.b*y.d)%MOD;
    r.c = (x.c*y.a)%MOD + (x.d*y.c)%MOD;
    r.d = (x.c*y.b)%MOD + (x.d*y.d)%MOD;
    return r;
}

Mat putere(Mat m, long long k)
{
    if(k == 0)
        return (Mat){1,0,0,1}; 
    if(k == 1)
        return m;
    Mat p = putere(m, k/2);
    p = inmultire(p, p);
    if(k%2)
        p = inmultire(p, m);
    return p;
}

long long k_fib(long long k)
{
    if(k == 0)
        return 0;
    Mat M = {1,1,1,0};
    Mat R = putere(M, k);
    return R.b;
}

int main(void)
{
    FILE* f,*g;
    long long k;
    if((f=fopen("kfib.in","r"))==NULL)
    {
        printf("fisierul de intrare nu a putut fi deschis\n");
        exit(EXIT_FAILURE);
    }
    if((g=fopen("kfib.out","w"))==NULL)
    {
        printf("fisierul de iesire nu a putut fi deschis\n");
        exit(EXIT_FAILURE);
    }
    if(fscanf(f,"%lld",&k)!=1)
    {
        printf("citire din fisier nereusita\n");
        exit(EXIT_FAILURE);
    }
    fscanf(f,"%lld",&k);
    long long tk=k_fib(k);
    fprintf(g,"%lld\n",tk);
    if(fclose(f)<0)
    {
        printf("fisierul de intrare nu a putut fi inchis\n");
        exit(EXIT_FAILURE);
    }
    if(fclose(g)<0)
    {
        printf("fisierul de iesire nu a putut fi inchis\n");
        exit(EXIT_FAILURE);
    }
    return 0;
}