#include <fstream>
using namespace std;

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

void inmultire(long long rez[0][5], long long m[][5])
{
    long long a = rez[0][0], b = rez[0][1], c = rez[1][0], d = rez[1][1];
    long long e = m[0][0], f = m[0][1], g = m[1][0], h = m[1][1];
    rez[0][0] = (a * e + b * g) % 666013;
    rez[0][1] = (a * f + b * h) % 666013;
    rez[1][0] = (c * e + d * g) % 666013;
    rez[1][1] = (c * f + d * h) % 666013;
}

int main()
{
    int k;
    fin >> k;

    long long m[5][5];
    m[0][0] = 0;
    m[0][1] = m[1][0] = m[1][1] = 1;

    long long rez[5][5];
    rez[0][0] = rez[1][1] = 1;
    rez[0][1] = rez[1][0] = 0;

    while (k)
    {
        if (k % 2)
            inmultire(rez, m);
        inmultire(m, m);

        k /= 2;
    }

    fout << rez[0][1];
    return 0;
}