Function f(n) is given with recurrent relation:
Find the value of f(n) mod 123456789.
One positive integer n (1≤n≤109).
Print the value of f(n) mod 123456789.