Problems
Function f(n)
Function f(n)
Function f(n) is given with recurrent relation:
f(n) = f(n-1) + f(n - 2) + ... + f(2) + f(1),
f(1) = 1
Find the value of f(n)~mod~123456789.
Input data
One positive integer n~(1 \le n \le 10^9).
Output data
Print the value of f(n)~mod~123456789.
Examples
Input example #3
3
Output example #3
2
Input example #4
10
Output example #4
256