#include <fstream>

using namespace std;

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

const long long MOD = 666013;
long long k, X[2][2], Sol[2][2];

void Multiply(long long A[2][2], long long B[2][2])
{
    long long aux00, aux01, aux10, aux11;
    aux00 = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    aux01 = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    aux10 = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    aux11 = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
    A[0][0] = aux00;
    A[0][1] = aux01;
    A[1][0] = aux10;
    A[1][1] = aux11;
}

void Lg_Put(long long p)
{
    while (p)
    {
        if (p & 1) Multiply(Sol, X);
        Multiply(X, X);
        p >>= 1;
    }
}

int main()
{
    fin >> k;
    if (k < 2) fout << k << '\n';
    else
    {
        X[0][1] = X[1][0] = X[1][1] = 1;
        Sol[0][0] = Sol[1][1] = 1;
        Lg_Put(k - 1);
        fout << Sol[1][1] << '\n';
    }

    fout.close();
    return 0;
}