← 返回题目列表

AtCoder · yahoo_procon2019_final_e

E. 间谍活动

中文机器翻译题面 查看原题

配点 : 1100 点

問題文

N 的 您可以创建一个包含 M 有一栋多层建筑。忍者高桥君决定进入所有建筑的每一层。最开始,高桥君在 1 号建筑的 1 层,最终想要再次回到 1 号建筑的 1 层。

高桥君可以进行以下 2 种移动。

  • 通过楼梯移动到同一栋建筑的相邻楼层。
  • 瞬间转移到另一栋建筑的相同楼层。

由于在建筑内停留时间过长可能会被发现,所以在途中不要进入同一栋建筑的同一楼层超过 2 次, 1 号建筑的 1 层。

移动的方法有多少种, 10^9+7 求以 的余数。

制約

  • 2 ≤ N ≤ 100
  • 2 ≤ M ≤ 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M

出力

移动方法的总数由 10^9+7 取余的结果。 由于是


入力例 1

3 2

出力例 1

6

下一步 6 有一条街。 转至 (i,j) 是 您也可以写 i 号建筑的 j 表示楼层。

  • (1,1) → (2,1) → (3,1) → (3,2) → (2,2) → (1,2) → (1,1)
  • (1,1) → (3,1) → (2,1) → (2,2) → (3,2) → (1,2) → (1,1)
  • (1,1) → (3,1) → (3,2) → (1,2) → (2,2) → (2,1) → (1,1)
  • (1,1) → (1,2) → (2,2) → (3,2) → (3,1) → (2,1) → (1,1)
  • (1,1) → (1,2) → (3,2) → (2,2) → (2,1) → (3,1) → (1,1)
  • (1,1) → (2,1) → (2,2) → (1,2) → (3,2) → (3,1) → (1,1)

入力例 2

98 7654321

出力例 2

257361229