#include <iostream>
#define SQR(a) ((a * a) % m)
#define SUM(a, b) ((a + b) % m)
#define MUL(a, b) ((a * b) % m)
#define SUB(a, b) ((a - b) % m)
using namespace std;

typedef long long num;

const num m = 666013, period = 1332028; // precomputed for given m

// ifstream cin("kfib.in");
// ofstream cout("kfib.out");

void fib(num k, num res[])
{
    if (k == 0)
    {
        res[0] = 0;
        res[1] = 1;
    }
    else
    {
        fib(k / 2, res);
        num a = res[0],
            b = res[1];
        // cout << a << " " << b << endl;
        // cout << k / 2 << " " << MUL(2ll, b) << " " << SUB(MUL(2ull, b), a) << " " << MUL(SUB(MUL(2ull, b), a), a) << endl;
        num c = a * (2 * b - a) % m;
        num d = (a * a + b * b) % m;
        if (k % 2 == 0)
        {
            res[0] = c;
            res[1] = d;
        }
        else
        {
            res[0] = d;
            res[1] = SUM(c, d);
        }
    }
}

int main()
{
    num k, res[] = {0, 0};
    cin >> k;
    fib(k, res);
    cout << (res[0] + m) % m;
}