#include <iostream>
#include <fstream>
#define LL long long
#define MOD 666013

using namespace std;

struct matrix{
    LL a, b, c, d;
};

matrix c, my_unit;

matrix multiply(matrix a, matrix b)
{
    c.a = (a.a * b.a + a.b * b.c) % MOD;
    c.b = (a.a * b.b + a.b * b.d) % MOD;
    c.c = (a.c * b.a + a.d * b.c) % MOD;
    c.d = (a.c * b.b + a.d * b.d) % MOD;
    return c;
}

matrix power(matrix base, LL exponent)
{
    if(exponent == 0)
        return my_unit;
    if(exponent == 1)
        return base;
    if(exponent % 2)
        return multiply(base, (power(multiply(base, base), exponent / 2)));
    else
        return power(multiply(base, base), exponent / 2);
}

int main()
{
    matrix m, res;
    LL n;
    fstream f("kfib.in", ios::in);
    fstream g("kfib.out", ios::out);
    f >> n;
    my_unit.a = my_unit.d = 1;
    my_unit.b = my_unit.c = 0;
    m.a = 0;
    m.b = m.c = m.d = 1;
    if(n >= 1){
        res = power(m, n-1);
        g << res.d % MOD;
    }
    else
        g << 0;
    return 0;
}