#include <fstream>

using namespace std;

struct matrice
{
    long long a11, a12, a21, a22;
};

matrice produs(matrice a, matrice b)
{
    return {a.a11 * b.a11 + a.a21 * b.a21,
    a.a11 * b.a12 + a.a21 * b.a22,
    a.a21 * b.a11 + a.a22 * b.a21,
    a.a21 * b.a12 + a.a22 * b.a22};
}

matrice modulo(matrice a)
{
    return {a.a11 % 666013, a.a12 % 666013, a.a21 % 666013, a.a22 % 666013};
}

matrice exponentiere(matrice a, int n)
{
    if(n == 1)
        return modulo(a);
    if(n % 2 == 1)
        return modulo(produs(modulo(a), modulo(exponentiere(a, n-1))));
    else
        return modulo(exponentiere(modulo(produs(a, a)), n/2));
}



int main()
{
    long long n;
    matrice a = {0, 1, 1, 1};

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

    fin >> n;
    a = exponentiere(a, n-1);

    fout << a.a22;

    fin.close();
    fout.close();
    return 0;
}