Execution time limit is 1 second Runtime memory usage limit is 128 megabytes Function f(n) is given with recurrent relation:
Find the value of f(n) mod 123456789.
Input
One positive integer n (1≤n≤109).
Output
Print the value of f(n) mod 123456789.
Examples