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 capacity. However, China, as a socialist developing country, is not fully equipped to completely eradicate the virus. We can only focus on suppressing the reproduction of these rats. Currently, we are implementing reproductive suppression on these adult rats, which can reproduce one pair per month, such that the newly born pair of juvenile rats can only reproduce after 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 juvenile rats are highly resilient, and initially, there is only 1 pair of adult rats. Note: "Initially" refers to the starting point, not the first month.)

Input Format

Only one line: $m$ and $n$

Output Format

The result after taking modulo 123456789

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

【Data Range】

1 <= m <= 100

1 <= n <= 10^7

Source

CodesOnline