Функція f(n)#10165

Функція f(n)

1 секунда

128 мегабайтів

Дуже легка

Функція $f (n)$ визначена рекурентним співвідношенням:

f(n) = f(n-1) + f(n-2) + ... + f(2) + f(1),
f(1) = 1

Знайдіть значення $f (n) m o d 123456789$ f(n)~mod~123456789.

Вхідні дані

Дано одне натуральне число $n (1 \leq n \leq 1 0^{9})$ n~(1 \le n \le 10^9).

Виведіть значення $f (n) m o d 123456789$ f(n)~mod~123456789.

Приклад 3

Приклад 4