该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

美丽国企图利用老鼠传播病毒，这种老鼠繁殖能力极强。
初始时有 1 对成年老鼠（注意：这是第 0 个月的状态，而非第一个月）。
每对成年老鼠每个月可以繁殖出一对新的小老鼠，但新生的小老鼠需要经过 $m$ 个月后才具备繁殖能力（即在出生后的第 $m$ 个月起才成年并可以繁殖）。
假设老鼠生命力极强不会死亡，请你计算 $n$ 个月后，老鼠的总对数是多少。

输入格式

一行两个整数 $m, n$，用一个空格隔开。

输出格式

一行一个整数，表示 $n$ 个月后老鼠总对数对 $123456789$ 取模的结果。

样例

2 5

13

样例解释

$m=2$，即新生老鼠需 $2$ 个月后才成年。
第 0 个月：有 1 对成年鼠（初始），共 1 对。
第 1 个月：1 对成年鼠繁殖 1 对，总数为 $1 + 1 = 2$ 对。
第 2 个月：原来的 1 对成年鼠继续繁殖 1 对，且初始繁殖的那对现在刚成年（未繁殖），总数为 $2 + 1 = 3$ 对。
第 3 个月：成年鼠共 2 对（初始的 + 第 0 个月出生的），每对繁殖 1 对，总数为 $3 + 2 = 5$ 对。
第 4 个月：成年鼠共 3 对，总数为 $5 + 3 = 8$ 对。
第 5 个月：成年鼠共 5 对，总数为 $8 + 5 = 13$ 对。

因此第 5 个月后共有 13 对老鼠，输出 13。

数据范围

• $1 \le m \le 100$
• $1 \le n \le 10^7$