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

int K;
int rsp[2][2], act[2][2];

void resetMatrix()
{
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
        {
            act[i][j] = rsp[i][j];
            rsp[i][j] = 0;
        }
}

void rec(int put)
{
    if (put <= 1)
    {
        rsp[0][0] = 0, rsp[0][1] = 1, rsp[1][0] = 1, rsp[1][1] = 1;
        /// 0 1
        /// 1 1
        return;
    }
    if (put % 2 == 0)
    {
        rec(put / 2);
        resetMatrix();
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    rsp[i][j] = (rsp[i][j] + (1LL * act[i][k] * act[k][j]) % MOD) % MOD;
        return;
    }
    rec(put - 1);
    resetMatrix();
    rsp[0][0] = act[0][1];
    rsp[0][1] = rsp[1][0] = act[1][1];
    rsp[1][1] = act[1][0] + act[1][1];
}

int main()
{
    fin >> K;
    rec(K - 1);
    fout << rsp[1][1];
    return 0;
}