#include <fstream>

using namespace std;

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

const long long mod = 666013;
long long n;

long long fibo(long long x)
{
    if(x == 0)
        return 0;

    if(x <= 2)
        return 1;

    if(x % 2 == 0)
    {
        long long k = x / 2;
        long long f1 = fibo(k - 1);
        long long f2 = fibo(k);
        long long f3 = (f1 + f2) % mod;

        return (1LL * f2 * (f1 + f3) % mod) % mod;
    }

    else
    {
        long long k = (x - 1) / 2;
        long long f1 = fibo(k);
        long long f2 = fibo(k + 1);

        return ((1LL * f1 * f1) % mod + (1LL * f2 * f2) % mod) % mod;
    }
}

int main()
{
    f >> n;
    g << fibo(n);
    return 0;
}