#include <bits/stdc++.h>

using namespace std;
ifstream f ( "kfib.in" );
ofstream g ( "kfib.out" );
const int MOD = 666013;
int N, i;
int MAT[3][3], SOL[3][3];

void mult ( int A[][3], int B[][3], int C[][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;
}
void powlg ( int M[][3], int P )
{
    int C[3][3], AUX[3][3], i;
    memcpy ( C, MAT, sizeof ( MAT ) );
    M[0][0] = M[1][1] = 1;

    for ( i = 0; ( 1 << i ) <= P; i++ )
    {
        if ( P & ( 1 << i ) )
        {
            memset ( AUX, 0, sizeof ( AUX ) );
            mult ( M, C, AUX );
            memcpy ( M, AUX, sizeof ( AUX ) );
        }

        memset ( AUX, 0, sizeof ( AUX ) );
        mult ( C, C, AUX );
        memcpy ( C, AUX, sizeof ( C ) );
    }
}
int kfib ( int N )
{
    MAT[0][0] = 0;
    MAT[0][1] = MAT[1][0] = MAT[1][1] = 1;
    powlg ( SOL, N - 1 );
    return SOL[1][1];
}
int main()
{
    f >> N;
    g << kfib ( N );
    return 0;
}