#include <fstream>

using namespace std;

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

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

void Multiply(long long A[2][2], long long B[2][2])
{
    long long aux00 = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
    long long aux01 = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
    long long aux10 = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
    long long 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 Power(long long p)
{
    while (p > 0)
    {
        if (p & 1) Multiply(Sol, X);
        Multiply(X, X);
        p >>= 1;
    }
}

int main()
{
    fin >> k;

    Sol[0][0] = Sol[1][1] = 1;
    X[0][1] = X[1][0] = X[1][1] = 1;

    Power(k - 1);

    fout << (k < 2 ? k : Sol[1][1]) << '\n';

    fout.close();
    return 0;
}