Problems
Function f(n)
Function f(n)
Function $f(n)$ is given with recurrent relation:
\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}
Find the value of $f(n)~mod~123456789$.
\InputFile
One positive integer $n~(1 \le n \le 10^9)$.
\OutputFile
Print the value of $f(n)~mod~123456789$.
Input example #3
3
Output example #3
2
Input example #4
10
Output example #4
256