#include <fstream>

using namespace std;

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

const int MOD = 666013;

long long A[3][3], B[3][3], Z[3][3], k;

void inmulteste (long long X[3][3], long long Y[3][3])
{
    Z[1][1] = (((X[1][1] % MOD) * (Y[1][1] % MOD) % MOD) + ((X[1][2] % MOD) * (Y[2][1] % MOD)) % MOD) % MOD;
    Z[1][2] = (((X[1][1] % MOD) * (Y[1][2] % MOD) % MOD) + ((X[1][2] % MOD) * (Y[2][2] % MOD)) % MOD) % MOD;
    Z[2][1] = (((X[2][1] % MOD) * (Y[1][1] % MOD) % MOD) + ((X[2][2] % MOD) * (Y[2][1] % MOD)) % MOD) % MOD;
    Z[2][2] = (((X[2][1] % MOD) * (Y[1][2] % MOD) % MOD) + ((X[2][2] % MOD) * (Y[2][2] % MOD)) % MOD) % MOD;

    X[1][1] = Z[1][1];
    X[1][2] = Z[1][2];
    X[2][1] = Z[2][1];
    X[2][2] = Z[2][2];
}

int main()
{
    f >> k;

    A[1][1] = A[2][2] = 1;
    B[1][2] = B[2][1] = B[2][2] = 1;

    while (k)
    {
        if (k & 1)
            inmulteste (A, B);

        k /= 2;
        inmulteste (B, B);
    }

    g << A[2][1] % MOD;

    f.close ();
    g.close ();
    return 0;
}