[ABC345] G - Sugoroku 5

G - Sugoroku 5

Time Limit: 12 sec / Memory Limit: 1024 MB

题面

有一个棋盘游戏，共有 个方块：方块 ，方块 ，，方块 。
你有一个骰子，投掷结果为介于 到 之间的整数，每个结果出现的概率相等。
你从方块 开始。重复以下操作，直到到达方块 ：

• 投掷骰子。设当前在第 个方块，投掷结果为 ，那么移动到第 个方块。

设 表示经过恰好 次操作后到达方块 的概率。计算 对 取模。

概率取模 后的值是多少？可以证明所求概率始终为有理数。在本问题的约束下，也可以证明将这些值表示为 （其中 和 互质）时，存在唯一的整数 满足 且 。找出这个 。

限制条件

• 和 为整数。

---

输入

输入以标准输入给出，格式如下：

输出

输出 行。第 行应包含 对 取模后的值。

---

输入样例 1

3 2

输出样例 1

0
249561089
748683265

例如，当骰子的结果如下时，你会在恰好两次操作后到达方块 ：

• 第一次操作得到 ，第二次操作得到 。
• 第一次操作得到 ，第二次操作得到 。
• 第一次操作得到 ，第二次操作得到 。

因此，。我们有 ，因此输出 作为 。

---

输入样例 2

5 5

输出样例 2

598946612
479157290
463185380
682000542
771443236

---

输入样例 3

10 6

输出样例 3

0
166374059
207967574
610038216
177927813
630578223
902091444
412046453
481340945
404612686