/* 
 * 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 int Matrix[2][2];
Matrix X={ { 1, 0 }, { 0, 1 } };
inline void multiply( Matrix& X, Matrix Y )
{
    Matrix R;
    u i, j, k;
    R[0][0]=( (1LL*X[0][0]*Y[0][0] ) + (1LL*X[0][1] * Y[1][0] ) )%Modulo;
    R[0][1]=( (1LL*X[0][0]*Y[0][1] ) + (1LL*X[0][1] * Y[1][1] ) )%Modulo;
    R[1][0]=( (1LL*X[1][0]*Y[0][0] ) + (1LL*X[1][1] * Y[1][0] ) )%Modulo;
    R[1][1]=( (1LL*X[1][0]*Y[0][1] ) + (1LL*X[1][1] * Y[1][1] ) )%Modulo;
    X[0][0]=R[0][0]; X[0][1]=R[0][1];
    X[1][0]=R[1][0]; X[1][1]=R[1][1];
}
inline 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] );
}