Функция 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$ .

Входные данные

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

Выведите значение $f (n) m o d 123456789$ .

Ввод #3

Ответ #3

Ввод #4

Ответ #4

Отправки 2K

Коэффициент принятия 25 %