#include <fstream>

using namespace std;

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

#define MOD 666013

long long z[2][2], ans[2][2], copie[2][2];

int main() {
    int k, i, j;
    cin >> k;
    z[0][0] = 0;
    z[0][1] = 1;
    z[1][0] = 1;
    z[1][1] = 1;
    ans[0][0] = 1;
    ans[0][1] = 0;
    ans[1][0] = 0;
    ans[1][1] = 1;
    k--;
    while ( k > 0 ) {
        if ( k % 2 == 1 ) {
            for ( i = 0; i < 2; i++ )
                for ( j = 0; j < 2; j++ )
                    copie[i][j] = ans[i][j];
            ans[0][0] = ( z[0][0] * copie[0][0] + z[0][1] * copie[1][0] ) % MOD;
            ans[0][1] = ( z[0][0] * copie[0][1] + z[0][1] * copie[1][1] ) % MOD;
            ans[1][0] = ( z[1][0] * copie[0][0] + z[1][1] * copie[1][0] ) % MOD;
            ans[1][1] = ( z[1][0] * copie[0][1] + z[1][1] * copie[1][1] ) % MOD;
        }
        for ( i = 0; i < 2; i++ )
            for ( j = 0; j < 2; j++ )
                copie[i][j] = z[i][j];
        z[0][0] = ( copie[0][0] * copie[0][0] + copie[0][1] * copie[1][0] ) % MOD;
        z[0][1] = ( copie[0][0] * copie[0][1] + copie[0][1] * copie[1][1] ) % MOD;
        z[1][0] = ( copie[1][0] * copie[0][0] + copie[1][1] * copie[1][0] ) % MOD;
        z[1][1] = ( copie[1][0] * copie[0][1] + copie[1][1] * copie[1][1] ) % MOD;
        k /= 2;
    }
    cout << ans[1][1];
    return 0;
}