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

using namespace std;

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

    int 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");

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

    return 0;
}