#include <fstream>
#define mod 666013
using namespace std;
ofstream fout ("kfib.out");
ifstream fin ("kfib.in");
long long ans[3][3],mat[3][3],aux[3][3],k;
void inmult( long long A[][3] , long long B[][3] );
int main()
{
    ans[ 1 ][ 2 ] = 1;
    ans[ 2 ][ 1 ] = 1;
    ans[ 2 ][ 2 ] = 1;
    mat[ 1 ][ 1 ] = 1;
    mat[ 2 ][ 2 ] = 1;
    fin>>k;
    k++;
    while( k > 1 )
    {
        if( k % 2 )
        {
            k--;
            inmult( mat , ans );
        }
        else
        {
            k /= 2;
            inmult( ans , ans );
        }
    }
    inmult( ans , mat );
    fout<<ans[ 1 ][ 1 ];
}
void inmult( long long A[][3] , long long B[][3] )
{
    aux[ 1 ][ 1 ] = ( ( A[ 1 ][ 1 ] * B[ 1 ][ 1 ] ) % mod + ( A[ 1 ][ 2 ] * B[ 2 ][ 1 ] ) % mod ) % mod;
    aux[ 1 ][ 2 ] = ( ( A[ 1 ][ 1 ] * B[ 1 ][ 2 ] ) % mod + ( A[ 1 ][ 2 ] * B[ 2 ][ 2 ] ) % mod ) % mod;
    aux[ 2 ][ 1 ] = ( ( A[ 2 ][ 1 ] * B[ 1 ][ 1 ] ) % mod + ( A[ 2 ][ 2 ] * B[ 2 ][ 1 ] ) % mod ) % mod;
    aux[ 2 ][ 2 ] = ( ( A[ 2 ][ 1 ] * B[ 1 ][ 2 ] ) % mod + ( A[ 2 ][ 2 ] * B[ 2 ][ 2 ] ) % mod ) % mod;
    A[ 1 ][ 1 ] = aux[ 1 ][ 1 ];
    A[ 1 ][ 2 ] = aux[ 1 ][ 2 ];
    A[ 2 ][ 1 ] = aux[ 2 ][ 1 ];
    A[ 2 ][ 2 ] = aux[ 2 ][ 2 ];
}