//
//  main.c
//  kfib_TPA
//
//  Created by Bran Eduard Denis on 31.05.2023.
//

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

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

}


void putere(long long int a[2][2],long long int b[2][2], long long int n)
{
    
    while(n>0)
    {
        if(n%2==1)
            inmult_matrici(b,a);
        inmult_matrici(a,a);
        n=n/2;
    }
}

int main() {

    long long int a[2][2],b[2][2];
    int n;
    FILE *f;
    f=fopen("kfib.in","rt");
    if(f==NULL)
    {
        printf("Eroare");
        return 0;
    }
    fscanf(f,"%d",&n);
    f=fopen("kfib.out","wt");
    if(f==NULL)
    {
        printf("Eroare");
        return 0;
    }
    a[0][0]=0;
    a[0][1]=1;
    a[1][0]=1;
    a[1][1]=1;
    
    b[0][0]=1;
    b[0][1]=0;
    b[1][0]=0;
    b[1][1]=1;
    
    putere(a,b,n);
    fprintf(f,"%lld",b[0][1]);
    return 0;
}