Функція f(n)

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

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

Знайдіть значення $f(n)mod123456789$.

Вхідні дані

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

Вихідні дані

Виведіть значення $f(n)mod123456789$.

Приклади