import string
from dataclasses import dataclass
import sys

# Increase the limit for integer string conversions
sys.set_int_max_str_digits(100000000)  # You can set this to a higher number if needed

@dataclass(frozen=True)
class Constants:
    INPUT: string = "/Users/lucadani/PycharmProjects/InfoArenaPython/Al_Klea_Termen_Fibonacci/kfib.in"
    OUTPUT: string = "/Users/lucadani/PycharmProjects/InfoArenaPython/Al_Klea_Termen_Fibonacci/kfib.out"


# Function to multiply two matrices
def matrix_multiply(A, B):
    return [
        [A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
        [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]
    ]


# Function to perform matrix exponentiation
def matrix_power(M, power):
    # Start with the identity matrix
    result = [[1, 0], [0, 1]]
    base = M

    while power > 0:
        if power & 1:
            result = matrix_multiply(result, base)
        base = matrix_multiply(base, base)
        power >>= 1

    return result


def fibo(k):
    if k in range(0, 2):
        return k

    # The transformation matrix
    M = [[1, 1], [1, 0]]

    # Get M^(k-1)
    M_k_minus_1 = matrix_power(M, k - 1)

    # The k-th Fibonacci number is in the top left of the resulting matrix
    return M_k_minus_1[0][0] % 666013


if __name__ == "__main__":
    with open(Constants.INPUT, "r") as file:
        k = int(file.readline().strip())

    with open(Constants.OUTPUT, "w") as file:
        file.write(str(fibo(k)))