#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;

typedef vector < vector < int > > Matrix;

int n;

Matrix m;

void Resize(Matrix &a)
{
    a.resize(2);
    a[0].resize(2);
    a[1].resize(2);
}

Matrix inm(Matrix a, Matrix b)
{
    Matrix c;
    Resize(c);


    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                c[i][j] += (1LL * a[i][k] * b[k][j]) % MOD;

    return c;
}

Matrix epq(Matrix a, int p)
{
    if (p == 1)
        return a;

    if (p % 2)
        return inm(a, epq(inm(a, a), p >> 1));

     return epq(inm(a, a), p >> 1);
}
int main()
{
    fin >> n;

    Resize(m);

    m[0][0] = 0;
    m[0][1] = m[1][0] = m[1][1] = 1;

    fout << (epq(m, n - 1))[1][1] % MOD;

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