// K Fib.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>

constexpr long long MOD = 666013;
// 1000000007

// 0 1
// 2 3

long long modularMultiply(long long a, long long b)
{
    a %= MOD;
    b %= MOD;
    return (a * b) % MOD;
   /* long long result = 0;

    if (a == 0 || b == 0)
        return 0;
    if (a == 1)
        return b;
    if (b == 1)
        return a;

    while (b) {
        if (b & 0x1)
        {
            result += a;
            result %= MOD;
        }
        b >>= 1;
        if (a < MOD - a)
        {
            a <<= 1;
        }
        else
        {
            a -= (MOD - a);
        }
    }
    return result;*/
    /*long long res = 0;
    a %= MOD;
    while (b) {
        if (b & 1)
            res = (res + a) % MOD;
        a = (a + a) % MOD;
        b >>= 1;
    }
    return res;*/
}

struct fibonacciMatrix
{
    long long tl, tr, bl, br;

    fibonacciMatrix operator* (const fibonacciMatrix& b) const
    {
        fibonacciMatrix result {};
        result.tl = (modularMultiply(this->tl, b.tl) + modularMultiply(this->tr, b.bl)) % MOD;
        result.tr = (modularMultiply(this->tl, b.tr) + modularMultiply(this->tr, b.br)) % MOD;
        result.bl = (modularMultiply(this->bl, b.tl) + modularMultiply(this->br, b.bl)) % MOD;
        result.br = (modularMultiply(this->bl, b.tr) + modularMultiply(this->br, b.br)) % MOD;
        return result;
    }

    void operator= (const fibonacciMatrix& b)
    {
        this->bl = b.bl;
        this->br = b.br;
        this->tl = b.tl;
        this->tr = b.tr;
    }
};

fibonacciMatrix squareExponentiation(fibonacciMatrix matrix, int exponent) {
	fibonacciMatrix result = matrix;
    //int a = 14'472'334'024'676'221 // 79th fib;

    int count = 0;
    for (;; count++) {

        if (count == 5)
            count--;
        if (exponent & 1)
            result = result * matrix;

        if (!exponent)
            break;

        exponent >>= 1;

        matrix = matrix * matrix;
    }
    return result;
}

long long fibonacci(int k)
{
    fibonacciMatrix a;
    a.tl = 1;
    a.tr = 1;
    a.bl = 1;
    a.br = 0;

    const auto aux = squareExponentiation(a, k - 1);

	return aux.tr;
}

int main()
{
    std::ifstream f("kfib.in");
    std::ofstream g("kfib.out");
    int k;
    f >> k;
    const auto a = fibonacci(k);
    g << a;
    std::cout << a;
}