#include <fstream>
using namespace std;
long long prod[2][2];

void produsmatrici(long long a[2][2], long long b[2][2])
{
    int i, j;
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            prod[i][j] = (a[i][0]*b[0][j] + a[i][1]*b[1][j]) % 666013;
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            a[i][j] = prod[i][j];
}

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    int i, n;
    fin >> n;

    long long a[2][2];
    a[0][0] = 1;
    a[0][1] = 0;
    a[1][0] = 0;
    a[1][1] = 1;
    long long b[2][2];
    b[0][0] = 0;
    b[0][1] = 1;
    b[1][0] = 1;
    b[1][1] = 1;

    for (i = 0; i < 30; i++)
    {
        if (1<<i & n)
            produsmatrici(a,b);
        produsmatrici(b,b);
    }
    fout << a[0][1];
    fin.close();
    fout.close();
    return 0;
}