MOD = 1_234_567_891
INV2 = (MOD + 1) // 2
TARGET_N = 1_000_000_000_000_000_003


def normalize(value):
    return value % MOD


def sub_mod(lhs, rhs):
    return lhs - rhs if lhs >= rhs else lhs + MOD - rhs


def mul_mod(lhs, rhs):
    return (lhs * rhs) % MOD


class Field:
    __slots__ = ("c",)

    def __init__(self, c0=0, c1=0, c2=0, c3=0):
        self.c = (
            normalize(c0),
            normalize(c1),
            normalize(c2),
            normalize(c3),
        )

    def is_base(self):
        return self.c[1] == 0 and self.c[2] == 0 and self.c[3] == 0

    def is_rho_multiple(self):
        return self.c[0] == 0 and self.c[2] == 0 and self.c[3] == 0

    def __neg__(self):
        return Field(*(0 if x == 0 else MOD - x for x in self.c))

    def __sub__(self, other):
        return Field(*(sub_mod(self.c[i], other.c[i]) for i in range(4)))

    def __mul__(self, other):
        product = [0] * 7
        for i in range(4):
            for j in range(4):
                product[i + j] = (product[i + j] + self.c[i] * other.c[j]) % MOD

        for i in range(6, 3, -1):
            product[i - 4] = (product[i - 4] + 2 * product[i]) % MOD

        return Field(product[0], product[1], product[2], product[3])

    def __eq__(self, other):
        return self.c == other.c


RHO = Field(0, 1, 0, 0)
INV_RHO = Field(0, 0, 0, INV2)


def square(value):
    return value * value


def cube(value):
    return value * value * value


def get_value(block, center, index):
    offset = index - center
    assert -4 <= offset <= 4
    return block[offset + 4]


def odd_value(block, center, k):
    return (
        get_value(block, center, k + 1) * cube(get_value(block, center, k - 1))
        - get_value(block, center, k - 2) * cube(get_value(block, center, k))
    )


def even_value(block, center, k):
    return (
        get_value(block, center, k)
        * INV_RHO
        * (
            get_value(block, center, k + 2)
            * square(get_value(block, center, k - 1))
            - get_value(block, center, k - 2)
            * square(get_value(block, center, k + 1))
        )
    )


def advance(block, center, bit):
    previous = block
    previous_center = center
    next_center = 2 * center + bit
    next_block = []

    for offset in range(-4, 5):
        index = next_center + offset
        if index % 2 == 0:
            next_block.append(even_value(previous, previous_center, index // 2))
        else:
            next_block.append(odd_value(previous, previous_center, (index + 1) // 2))

    return next_block, next_center


def eds_value(n):
    assert n > 0

    block = [
        Field(1),
        -RHO,
        Field(-1),
        Field(0),
        Field(1),
        RHO,
        Field(-1),
        Field(0, -2, 0, 0),
        Field(-3),
    ]
    center = 1

    for bit_index in range(n.bit_length() - 2, -1, -1):
        block, center = advance(block, center, (n >> bit_index) & 1)

    return block[4]


def sequence_value(n):
    value = eds_value(n)
    if n & 1:
        assert value.is_base()
        if (((n - 1) // 2) & 1) == 0:
            return value.c[0]
        return 0 if value.c[0] == 0 else MOD - value.c[0]

    assert value.is_rho_multiple()
    if (((n - 2) // 2) & 1) == 0:
        return value.c[1]
    return 0 if value.c[1] == 0 else MOD - value.c[1]


def direct_value(n):
    a = [0] * (n + 5)
    a[1] = 1
    a[2] = 1
    a[3] = 1
    a[4] = 2

    for k in range(3, n - 1):
        u = 1 if k % 2 == 0 else 2
        left = mul_mod(a[k], a[k])
        right = mul_mod(u, mul_mod(a[k + 1], a[k - 1]))
        denominator = a[k - 2]
        assert denominator != 0
        a[k + 2] = mul_mod(sub_mod(left, right), pow(denominator, MOD - 2, MOD))

    return a[n]


def run_checkpoints():
    assert square(square(RHO)) == Field(2)
    for n in range(1, 201):
        assert sequence_value(n) == direct_value(n)
    assert sequence_value(13) == 23_321
    assert direct_value(1003) == 231_906_014
    assert sequence_value(1003) == 231_906_014


if __name__ == "__main__":
    run_checkpoints()
    print(sequence_value(TARGET_N))