配点 : 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