#include <stdio.h>
#include <stdlib.h>
long long **inmultire(long long **A,long long **B)
{
    long long **C = (long long **)malloc(2 * sizeof(long long *));
    for (int i = 0; i < 2; i++) 
    {
        C[i] = (long long *)malloc(2 * sizeof(long long));
    }
    C[0][0]=(A[0][0]*B[0][0]%666013 + A[0][1]*B[1][0]%666013)%666013;
    C[0][1]=(A[0][0]*B[0][1]%666013 + A[0][1]*B[1][1]%666013)%666013;
    C[1][0]=(A[1][0]*B[0][0]%666013 + A[1][1]*B[1][0]%666013)%666013;
    C[1][1]=(A[1][0]*B[0][1]%666013 + A[1][1]*B[1][1]%666013)%666013;
    return C;
}
long long **exp_log_rec(long long **Z, long long n)
{
    long long **C = (long long **)malloc(2 * sizeof(int *));
    for (int i = 0; i < 2; i++) 
    {
        C[i] = (long long *)malloc(2 * sizeof(long long));
    }
    if(n<0) return NULL;
    if(n == 0)
    {
        C[0][0]=1;
        C[0][1]=0;
        C[1][0]=0;
        C[1][1]=1;
        return C;
    }
    C=exp_log_rec(inmultire(Z,Z),n/2);
    if(n % 2 == 0) return C;
    if(n % 2 == 1) return inmultire(Z ,C);
    return NULL;
}
int main(void)
{
    FILE *f=NULL,*g=NULL;
    int n,x;
    long long **Z=NULL,**C=NULL;
    Z=(long long**)(malloc(2*sizeof(long long*)));
    //M=(long long**)(malloc(sizeof(long long*)));
    for (int i = 0; i < 2; i++) 
    {
        Z[i] = (long long *)malloc(2 * sizeof(long long));
        //M[i]=(long long*)malloc(2*sizeof(long long));
    }
    Z[0][0]=0;
    Z[0][1]=1;
    Z[1][0]=1;
    Z[1][1]=1;
    if((f=fopen("kfib.in","r"))==NULL)
    {
        perror(NULL);
        exit(-1);
    }
    if((g=fopen("kfib.out","w"))==NULL)
    {
        perror(NULL);
        exit(-1);
    }
    fscanf(f,"%d",&n);
    if(fclose(f)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    C=exp_log_rec(Z,n-1);
    /*for(int i=0;i<=1;i++)
    {
        for(int j=0;j<=1;j++)
            printf("%d ",C[i][j]);
        printf("\n");
    }
    printf("%lld %lld\n",M[0][0],M[0][1]);*/
    fprintf(g,"%lld",C[1][1]);
    if(fclose(g)!=0)
    {
        perror(NULL);
        exit(-1);
    }
    free(Z);
    free(C);
    return 0;
}