#include <fstream>
using namespace std;

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

typedef int matfib[2][2];
const int r = 666013;

void inmul(matfib a, matfib b, matfib c)
{
    int i, j, k;
    for (i = 0; i<2; i++)
        for (j = 0; j<2; j++)
            c[i][j] = 0;
    for (i = 0; i<2; i++)
        for (j = 0; j<2; j++)
            for (k = 0; k<2; k++)
                c[i][j] = (c[i][j] + 1ll*a[i][k]*b[k][j])%r;
}

void copymat(matfib a, matfib b)
{
    a[0][0] = b[0][0];
    a[0][1] = b[0][1];
    a[1][0] = b[1][0];
    a[1][1] = b[1][1];
}

void exp(matfib a, int e, matfib rez)
{
    rez[0][0] = rez[1][1] = 1; //asta e un fel de element neutru, echivalentul lui 1 la exponentiere obisnuita
    matfib aux;
    while (e > 0)
    {
        if (e&1)
        {
            copymat(aux, rez);
            inmul(aux, a, rez);
        }
        copymat(aux, a);
        inmul(aux, aux, a);
        e >>= 1;
    }
}

int main()
{
    int N;
    fin >> N;
    matfib init;
    //initial am F0 = 0, F1 = 1;
    //am matricea (Fn-1, Fn-2) => (F1, F0) = (1, 0)
    //adica aia pe care o ridic la N-1 este
    // (1  1)
    // (1  0)
    init[0][0] = init[0][1] = init[1][0] = 1;
    init[1][1] = 0;
    matfib s;
    exp(init, N-1, s);
    fout << s[0][0];
    return 0;
}