/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 20, 2010, 4:52 PM
 */
#include <cstdio>
#define Modulo 666013

/*
 *
 */ 
using namespace std;
typedef unsigned int u;
typedef unsigned long long Matrix[2][2];
Matrix X={ { 1, 0 }, { 0, 1 } };
void multiply( Matrix& X, Matrix Y )
{
    Matrix R;
    u i, j, k;
    for( i=0; i < 2; ++i )
        for( j=0; j < 2; ++j )
        {
            R[i][j]=0;
            for( k=0; k < 2; ++k )
                R[i][j]=( R[i][j] + X[i][k]*Y[k][j] )%Modulo;
        }
    for( i=0; i < 2; ++i )
        for( j=0; j < 2; ++j )
            X[i][j]=R[i][j];
}
void pow( u p )
{
    Matrix Y={ { 0, 1 }, { 1, 1 } };
    while( p  )
    {
        if( p&1 )
        {
            --p;
            multiply( X, Y );
        }
        multiply( Y, Y );
        p>>=1;
    }
}
int main()
{u k;
    fscanf( fopen("kfib.in", "rt"), "%u", &k );
    pow( k-1 );
    fprintf( fopen("kfib.out", "wt"), "%u", X[1][1] );
}