#include <stdio.h>

#define MODULO 666013

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

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

long long int ridicare_putere_matr(int n)
{
    while(n)
    {
        if(n%2!=0)
        {
            inmultire_matrici(a,b);
        }
        n=n/2;
        inmultire_matrici(b,b);
    }
    return a[0][1];
}

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;

    fprintf(f2 , "%lld" , ridicare_putere_matr(n));

    return 0;
}