#include <fstream>
using namespace std;

const int MOD = 666013;

void matcopy(int to[2][2], int from[2][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            to[i][j] = from[i][j];
}

void matmul(int a[2][2], int b[2][2], int res[2][2])
{
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            res[i][j] = 0;
            for (int k = 0; k < 2; ++k)
            {
                res[i][j] = (res[i][j] + 1LL * a[i][k] * b[k][j]) % MOD;
            }
        }
    }
}

void lgput(int mat[2][2], int pw)
{
    // punem in res rezultatul pentru mat^pw
    // initializam res cu I_2
    int res[2][2] = {{1, 0}, {0, 1}};
    int temp[2][2];

    while (pw)
    {
        if (pw % 2 == 1)
        {
            matmul(res, mat, temp);
            matcopy(res, temp);
        }

        matmul(mat, mat, temp);
        matcopy(mat, temp);
        pw /= 2;
    }

    // copiez res in mat, pentru a salva solutia
    matcopy(mat, res);
}

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    int K;
    in >> K;

    // raspunsul va fi in A^(n-1) * col
    int A[2][2] = {{0, 1}, {1, 1}};
    // int col[2] = {0, 1};

    lgput(A, K);
    int fib_k = A[0][1];

    out << fib_k << "\n";

    return 0;
}