#include <fstream>

using namespace std;

const int kMod = 666013;

void Copiaza(int src[][2], int dest[][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            dest[i][j] = src[i][j];
}

void Inmulteste(int a[][2], int b[][2], int c[][2])
{
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            c[i][j] = 0;
            for (int k = 0; k < 2; ++k) {
                c[i][j] += 1LL * a[i][k] * b[k][j] % kMod;
                c[i][j] %= kMod;
            }
        }
    }
}

void Putere(int mat[][2], int p)
{
    if (p <= 1) return;

    int c[2][2];
    Copiaza(mat, c);

    if (p % 2 == 0) {
        Putere(c, p / 2);
        Inmulteste(c, c, mat);
    } else {
        int c2[2][2];
        Copiaza(mat, c2);

        Putere(c, p - 1);
        Inmulteste(c, c2, mat);
    }
}

int KFib(int n)
{
    if (n <= 2) return 1;

    int mat[][2] = {{0, 1}, {1, 1}};
    Putere(mat, n - 1);

    int fib[2][2] = {{1}, {1}};
    int rezultat[2][2];
    Inmulteste(mat, fib, rezultat);

    return rezultat[0][0];
}

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

    int n;
    fin >> n;

    fout << KFib(n);
    return 0;
}