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)mod123456789$.

Input

One positive integer $n(1\le n\le 10^9)$.

Output

Print the value of $f(n)mod123456789$.

Examples