#include <fstream>

using namespace std;

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

#define NUM 666013

struct Matrix {
    long long a, b, c, d;
};

const Matrix Z = {0, 1, 1, 1};

Matrix mult(Matrix x, Matrix y)
{
    Matrix result;

    result.a = (x.a * y.a + x.b * y.c) % NUM;
    result.b = (x.a * y.b + x.b * y.d) % NUM;
    result.c = (x.c * y.a + x.d * y.c) % NUM;
    result.d = (x.c * y.b + x.d * y.d) % NUM;

    return result;
}

Matrix powerZ(unsigned int p)
{
    if (p == 1) return Z;

    Matrix half = powerZ(p / 2);
    Matrix res = mult(half, half);

    if (p % 2 == 1) res = mult(res, Z);

    return res;
}

long long kfib(unsigned int k)
{
    if (k == 0) return 0;

    Matrix r = powerZ(k - 1);

    return r.d;
}

int main(void)
{
    unsigned int k;
    
    fin >> k;
    fout << kfib(k);

    fin.close();
    fout.close();

    return 0;
}