#include <fstream>
#include <iostream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD = 666013;
struct matrice
{
    long long a, b, c, d;
};
matrice x, y, z, i2, sol;
matrice Inmultire(matrice x, matrice y)
{
    matrice z;
    z.a = (x.a * y.a + x.b * y.c) % MOD;
    z.b = (x.a * y.b + x.b * y.d) % MOD;
    z.c = (x.c * y.a + x.d * y.c) % MOD;
    z.d = (x.c * y.b + x.d * y.d) % MOD;
    return z;
}
matrice putere(matrice x, int e, matrice i2)
{
    if(e == 0)
        return i2;
    if(e % 2 == 0){
        matrice aux = putere(x, e / 2, i2);
        return Inmultire(aux, aux);
    }
    else
        return Inmultire(x, putere(x, e - 1, i2));
}
int main()
{
    int v;
    in >> v;
    x.a = 0;
	x.b = 1;
    x.c = 1;
	x.d = 1;
    i2.a = 1;
	i2.b = 0;
    i2.c = 0;
	i2.d = 1;
    sol = putere(x, v, i2);
    out << sol.b;
    return 0;
}