#include <fstream>
#define MOD 666013

using namespace std;

struct matrice
{
    long long a, b, c, d;

    matrice(long long a = 0, long long b = 0, long long c = 0, long long d = 0): a(a), b(b), c(c), d(d)
    {

    }
};

ifstream fin("kfib.in");
ofstream fout("kfib.out");

matrice mult(matrice m1, matrice m2)
{
    matrice m3;
    m3.a = ((m1.a * m2.a) % MOD + (m1.b * m2.c) % MOD) % MOD;
    m3.b = ((m1.a * m2.b) % MOD + (m1.b * m2.d) % MOD) % MOD;
    m3.c = ((m1.c * m2.a) % MOD + (m1.d * m2.c) % MOD) % MOD;
    m3.d = ((m1.c * m2.b) % MOD + (m1.d * m2.d) % MOD) % MOD;

    return m3;
}

matrice powlog(long long pow)
{
    matrice x;
    if (pow == 1)
        return matrice(0, 1, 1, 1);
    else
    {
        x = powlog(pow/2);
        x = mult(x, x);
        if (pow % 2 == 1)
            x = mult(x, powlog(1));
        return x;
    }

}

int main()
{
    long long n;
    matrice x;

    fin >> n;
    x = powlog(n);

    fout << (x.b) << '\n';
    return 0;
}