Description

As is well known, the United States has attempted to use imperial rats to spread viruses in China... Their virus-carrying rats have a strong reproductive ability. However, China, as a socialist developing country, is not capable of completely eradicating the virus but can only focus on suppressing the reproduction of these rats. Currently, measures are taken to inhibit the reproduction of these adult rats, which can breed a pair of offspring every month, by delaying the breeding of newborn rat pairs for m months. Now, we need you, who are striving for the NOIP provincial first prize, to estimate the number of rat pairs after n months.

(Assume the young rats are highly resilient, and initially, there is only 1 pair of adult rats. Note: "Initially" means at the very beginning, not the first month.)

Input Format

Only one line: $m$ and $n$

Output Format

The result modulo 123456789

```input1 2 5 ``` ```output1 13 ``` ## Hint

【Data Range】

1 <= m <= 100

1 <= n <= 10^7

Source

CodesOnline