#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<long long, long long> cache;
const long long M = 666013;
long long fib(long long n)
{
    if (cache.count(n)) return cache[n];

    long long k = n / 2;
    if (n % 2 == 0) {
        return cache[n] = (fib(k) * fib(k) + fib(k - 1) * fib(k - 1)) % M;
    }
    return cache[n] = (fib(k) * fib(k + 1) + fib(k) * fib(k - 1)) % M;
}

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    long long n;
    in >> n;
    cache[0] = cache[1] = 1;
    long long sol = fib(n);
    out << sol << "\n";

    return 0;
}