#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

// int a[ai][aj] = {0, 1};
int ai = 2, aj = 2, bi = 2, bj = 2;

struct mat
{
    int mat[2][2];
};
mat multiply(mat a, mat b)
{
    mat result;

    result.mat[0][0] = (1LL * a.mat[0][0] * b.mat[0][0]) % 666013 + (1LL * a.mat[0][1] * b.mat[1][0]) % 666013;
    result.mat[0][1] = (1LL * a.mat[0][0] * b.mat[0][1]) % 666013 + (1LL * a.mat[0][1] * b.mat[1][1]) % 666013;
    result.mat[1][0] = (1LL * a.mat[1][0] * b.mat[0][0]) % 666013 + (1LL * a.mat[1][1] * b.mat[1][0]) % 666013;
    result.mat[1][1] = (1LL * a.mat[1][0] * b.mat[0][1]) % 666013 + (1LL * a.mat[1][1] * b.mat[1][1]) % 666013;

    return result;
}
void show(mat a)
{
    fout << a.mat[0][0] << " " << a.mat[0][1] << '\n'
         << a.mat[1][0] << " " << a.mat[1][1] << '\n';
}
mat pow(mat x, int n)
{
    mat p;
    p.mat[0][0] = 1;
    p.mat[0][1] = 0;
    p.mat[1][0] = 0;
    p.mat[1][1] = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            p = multiply(p, x);
            n--;
        }
        x = multiply(x, x);
        n /= 2;
    }
    return p;
}
int main()
{
    mat initmat;
    initmat.mat[0][0] = 0;
    initmat.mat[0][1] = 1;
    initmat.mat[1][0] = 1;
    initmat.mat[1][1] = 1;
    mat second = initmat;
    int n;
    fin >> n;

    mat m;
    // m.mat[1][1] = 1;
    fout << pow(initmat, n).mat[0][1];
    // show(pow(initmat, n));
    //  fout << a[0][0];

    return 0;
}