3173: 帝国老鼠病毒

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

众所周知，美丽国企图利用帝国老鼠到中国传染病毒…他的病毒老鼠繁殖能力很强，而中国对此早有防备，但处于社会主义发展中国家的我们并没有能力去彻底把病毒消灭，只能从抑制老鼠的繁殖入手，现对这种成年每个月可以繁殖一对的老鼠进行繁殖抑制，使出生的一对小老鼠要在 m 个月后才能繁殖，现在需要正在为 NOIP 省一等奖奋斗的你，对 n 个月后老鼠的对数进行评估？

（假设小老鼠的生命力顽强，且初始只有 1 对成年老鼠。 注：初始而并非第一个月）

Input

只有一行：$m$ 和 $n$

Output

对 123456789 取模后的结果

Sample Input Copy 

2 5

Sample Output Copy 

13

HINT

【数据范围】

1 <= m <= 100

1<= n <= 10^7