#include <fstream>

using namespace std;

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

const int mod = 666013;
int n;

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

    if(x <= 2)
        return 1;

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

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

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

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

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