#include <fstream>
#include <unordered_map>

using namespace std;

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

const int MOD = 666013;

int K;

unordered_map<int, int> mp;

static inline int Fibo(int n)
{
    if (n == 0)
        return 0;
    if (n <= 2)
        return 1;

    if (mp[n])
        return mp[n];

    if (n & 1)
    {
        int a = Fibo(n >> 1), b = Fibo((n >> 1) + 1);
        return (mp[n] = ((1LL * a * a) % (1LL * MOD) + (1LL * b * b) % (1LL * MOD)) % (1LL * MOD));
    }

    int a = Fibo((n >> 1) - 1), b = Fibo((n >> 1)), c = Fibo((n >> 1) + 1);
    return (mp[n] = ((1LL * a * b) % (1LL * MOD) + (1LL * b * c) % (1LL * MOD)) % (1LL * MOD));
}

int main()
{
    f.tie(nullptr);

    f >> K;

    g << Fibo(K) << '\n';

    return 0;
}