#include <fstream>

#define MOD 666013
#define int long long

using namespace std;

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

int k;
int x[2][2], a[2][2];

void putMat(int [2][2], int);
void inmultireMat(int [2][2], int [2][2], int [2][2]);

signed main()
{
    fin >>k;

    a[0][1] = a[1][0] = a[1][1] = 1;
    x[0][1] = 1;

    putMat(a, k);

    inmultireMat(x, a, x);

    fout <<x[0][0]<<'\n';

    fout.close();
    return 0;
}

void putMat(int a[2][2], int put)
{
    if (put == 1)
        return;

    int copie[2][2];
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            copie[i][j] = a[i][j];

    putMat(a, put/2);
    inmultireMat(a, a, a);
    if (put%2)
        inmultireMat(a, copie, a);
}

void inmultireMat(int a[2][2], int b[2][2], int c[2][2])
{
    int i, j, k;

    int rez[2][2];

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

    for (i = 0; i < 2; ++i)
        for (j = 0; j < 2; ++j)
            c[i][j] = rez[i][j];
}