Задачі
Функция f(n)
Функция f(n)
Функция $f(n)$ задана рекуррентным соотношением:
\begin{center}
\begin{lstlisting}[language=C++]
f(n) = f(n-1) + f(n - 2) + ... + f(2) + f(1),
f(1) = 1
\end{lstlisting}
\end{center}
Найдите значение $f(n)~mod~123456789$.
\InputFile
Одно натуральное число $n~(1 \le n \le 10^9)$.
\OutputFile
Выведите значение $f(n)~mod~123456789$.
Вхідні дані #3
3
Вихідні дані #3
2
Вхідні дані #4
10
Вихідні дані #4
256