#include <fstream>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");
long long a = 0, b = 1, c = 1, d = 1;
long long aa = 0, bb = 1, cc = 1, dd = 1;
int n;
int MOD = 666013;

void produsf()
{
    long long ax, bx, cx, dx;

    ax = ((aa * a) % MOD + (bb * c) % MOD) % MOD;
    bx = ((aa * b) % MOD + (bb * d) % MOD) % MOD;
    cx = ((cc * a) % MOD + (dd * c) % MOD) % MOD;
    dx = ((cc * b) % MOD + (dd * d) % MOD) % MOD;

    aa = ax;
    bb = bx;
    cc = cx;
    dd = dx;
}

void produsi()
{
    long long ax, bx, cx, dx;

    ax = ((a * a) % MOD + (b * c) % MOD) % MOD;
    bx = ((a * b) % MOD + (b * d) % MOD) % MOD;
    cx = ((c * a) % MOD + (d * c) % MOD) % MOD;
    dx = ((c * b) % MOD + (d * d) % MOD) % MOD;

    a = ax;
    b = bx;
    c = cx;
    d = dx;
}

int main()
{
    in>>n;

    if(n == 0)
    {
        out<<0;
        return 0;
    }

    n-=2;

    while(n != 0)
    {
        int r = n % 2;

        if(r == 1)
        {
            produsf();
        }

        produsi();
        n /= 2;
    }

    out<<dd;


    return 0;
}