#include <iostream>
#include <tuple>
#include <cstring>
#include <fstream>

const int mod = 666013;

using namespace std;

int X[2][2] = {{0,1},{1,1}};
int R[2][2] = {{1,0},{0,1}};

long K;

void Multiply (int A[2][2], int B[2][2])
{
    int C[2][2],i,j,k;

    memset (C, 0, sizeof(C));

    for (i = 0; i <= 1; i++)
        for (j = 0; j <= 1; j++)
    {
        C[i][j] = 0;
        for (k = 0; k <= 1; k++)
            C[i][j] = (C[i][j] + (A[i][k]*B[k][j])% mod) % mod;
    }

    memcpy (A, C, sizeof(C));
}

long result(int K)
{
    while(K > 0)
    {
        if (K % 2 == 1) Multiply(R,X);
        K = K / 2;
        Multiply(R,R);
    }
    return R[1][1];
}

int main()
{
    ifstream in ("kfib.in");
    ofstream out ("kfib.out");
    in >> K ;
    out << result(K);
    return 0;
}