#include <fstream>
#include <cstring>
using namespace std;

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

const int MOD = 666013;
int M[3][3];
int K;
int S[3][3];

void Inmultire( int a[3][3], int b[3][3], int c[3][3] );
void Power( int a[3][3], int P );

int main()
{
    int i, j;

    fin >> K;

    M[0][1] = M[1][0] = M[1][1] = 1;

    Power(S, K - 1);

    fout << S[1][1] << '\n';

    fin.close();
    fout.close();
    return 0;
}

void Inmultire( int a[3][3], int b[3][3], int c[3][3] )
{
    int i, j, k;

    for ( i = 0; i < 2; i++ )
        for ( j = 0; j < 2; j++ )
            for ( k = 0; k < 2; k++ )
                c[i][j] = ( c[i][j] + (( 1LL * a[i][k] * b[k][j] ) % MOD ) ) % MOD;
}

void Power( int a[3][3], int P )
{
    int aux[3][3], c[3][3];

    memcpy( c, M, sizeof(M) );
    a[0][0] = a[1][1] = 1;

    while ( P > 0 )
    {
        if ( P % 2 )
        {
            memset( aux, 0, sizeof(aux) );
            Inmultire( a, c, aux );
            memcpy( a, aux, sizeof(aux) );
            P--;
        }

        memset( aux, 0, sizeof(aux) );
        Inmultire( c, c, aux );
        memcpy( c, aux, sizeof(aux) );
        P /= 2;
    }
}