k = list(map(int, input().split()))[0]

import numpy as np

arr = np.array([0, 1])
const = np.array([[0, 1],
                 [1, 1]])

def exp_rap(a, p):
    if p == 0:
        return np.array([[1, 0],
                         [0, 1]])
    half = exp_rap(a, p // 2)
    if p % 2 == 0:
        return (half@half)%666013
    else:
        return (a@half@half)%666013

res_arr = (arr @ exp_rap(const, k - 1)) % 666013
print(res_arr[1])