#include <stdio.h>
#include <stdlib.h>
#define MO 666013

void Ridicare_Putere1(long long int A[1][2],long long int B[2][2])
{
    long long int C[1][2],i=0,j=0;
    for(i=0;i<2;i++)
    {
        C[0][i]=0;
        for(j=0;j<2;j++)
        {
            C[0][i]=(C[0][i]+A[0][j]*B[j][i])%MO;
        }
    }
    for(i=0;i<2;i++)
    {
        A[0][i]=C[0][i];
    }
}
void Ridicare_Putere2(long long int A[2][2],long long int B[2][2])
{
    long long int C[2][2],i=0,j=0,k=0;
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            C[i][j]=0;
            for(k=0;k<2;k++)
            {
                C[i][j]=(C[i][j]+A[i][k]*B[k][j])%MO;
            }
        }
    }
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
        {
            A[i][j]=C[i][j];
        }
    }
}
void kfib(FILE *fis,FILE *gis)
{
    long long int Z[2][2],M[1][2],k=0;
    fscanf(fis,"%lld",&k);
    Z[0][0]=0;
    Z[0][1]=1;
    Z[1][0]=1;
    Z[1][1]=1;
    M[0][0]=0;
    M[0][1]=1;
    while(k!=0)
    {
        if(k%2!=0)
        {
            Ridicare_Putere1(M,Z);
        }
        Ridicare_Putere2(Z,Z);
        k=k/2;
    }
    fprintf(gis,"%lld\n",M[0][0]);
}
int main(void)
{   
    FILE *fis=NULL,*gis=NULL;
    fis=fopen("kfib.in","r");
    if(fis==NULL)
    {
        perror("eroare la deschiderea fisierului de intrare\n");
        exit(-1);
    }
    gis=fopen("kfib.out","w");
    if(gis==NULL)
    {
        perror("eroare la deschiderea fisierului de iesire\n");
        exit(-1);
    }
    kfib(fis,gis);
    fclose(fis);
    fclose(gis);

    return 0;
}