eolymp
bolt
Try our new interface for solving problems
Problems

Function f(n)

Function f(n)

Time limit 1 second
Memory limit 128 MiB

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
Author Mykhailo Medvediev