#include <fstream>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

#define MOD 666013

int ans[2][2]={ { 0 , 1 } , { 1 , 1} },mat[2][2]={ { 1 , 0 } , { 0 , 1 } },i,j,n,k;

void _Multiply( int A[][2], int B[][2] )
{
    int C[2][2];
    C[ 0 ][ 0 ] = ( A[ 0 ][ 0 ] * B[ 0 ][ 0 ] + A[ 0 ][ 1 ] * B[ 1 ][ 0 ] ) % MOD;
    C[ 0 ][ 1 ] = ( A[ 0 ][ 0 ] * B[ 0 ][ 1 ] + A[ 0 ][ 1 ] * B[ 1 ][ 1 ] ) % MOD;
    C[ 1 ][ 0 ] = ( A[ 1 ][ 0 ] * B[ 0 ][ 0 ] + A[ 1 ][ 1 ] * B[ 1 ][ 0 ] ) % MOD;
    C[ 1 ][ 1 ] = ( A[ 1 ][ 0 ] * B[ 0 ][ 1 ] + A[ 1 ][ 1 ] * B[ 1 ][ 1 ] ) % MOD;

    A[ 0 ][ 0 ] = C[ 0 ][ 0 ];
    A[ 0 ][ 1 ] = C[ 0 ][ 1 ];
    A[ 1 ][ 0 ] = C[ 1 ][ 0 ];
    A[ 1 ][ 1 ] = C[ 1 ][ 1 ];
}

int main()
{
    in>>k;
    while( k > 1 )
    {
        if( k ^ 1 )
        {
            k /= 2;
            _Multiply( ans , ans );
        }
        else
        {
            --k;
            _Multiply( mat , ans );
        }
    }
    _Multiply( ans , mat );
    out<<ans[ 0 ][ 0 ];

return 0;
}