#include <stdio.h>

#define MODULO 666013

long long a[2][2] , b[2][2] , c[2][2];

void inmultire_matrici(long long int A[][2] , long long int B[][2])
{
    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])%MODULO;
            }
        }
    }
    for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
        {
            A[i][j]=C[i][j];
        }
    }
}

void ridicare_putere_matr(int n)
{
    while(n>0)
    {
        if(n%2==0)
        {
            n=n/2;
            inmultire_matrici(b,b);
        }
        else
        {
            n--;
            inmultire_matrici(a,b);
        }
    }
}

int main(void)
{
    int n;
    FILE *f1 , *f2;
    f1=fopen("kfib.in" , "r");
    f2=fopen("kfib.out" , "w");
    fscanf(f1 , "%d" , &n);

    ///matrcea a=[1 0 ; 0 1]
    a[0][0]=1;
    a[0][1]=0;
    a[1][0]=0;
    a[1][1]=1;

    ///matricea b=[0 1 ; 1 1]
    b[0][0]=0;
    b[0][1]=1;
    b[1][0]=1;
    b[1][1]=1;

    ///matricea c=[1 1 ; 0 0]
    c[0][0]=1;
    c[0][1]=1;
    c[1][0]=0;
    c[1][1]=0;

    ridicare_putere_matr(n-1);
    inmultire_matrici(c , a);
    fprintf(f2 , "%lld" , c[0][0]);

    return 0;
}