AT_yahoo_procon2019_final_e Espionage

有 $N$ 栋 $M$ 层的高楼。忍者高桥君打算潜入所有楼的所有楼层。最开始，高桥君在第 $1$ 栋楼的第 $1$ 层，并且最终他也要回到第 $1$ 栋楼的第 $1$ 层。 高桥君可以进行以下两种移动： - 通过楼梯在同一栋楼的相邻楼层之间移动。 - 在不同的楼之间瞬移到相同的楼层。 由于在同一栋楼的同一层停留时间过长容易被发现，因此在途中不能进入同一栋楼的同一层超过一次，并且最终要回到第 $1$ 栋楼的第 $1$ 层。 请计算有多少种不同的移动方式，答案对 $10^9+7$ 取模。

输入通过标准输入给出，格式如下： > $N$ $M$

输出移动方式的总数，对 $10^9+7$ 取模。

## 限制条件 - $2 \leq N \leq 100$ - $2 \leq M \leq 10^9$ - 输入均为整数。 ## 样例解释 1 共有如下 $6$ 种方式。$(i,j)$ 表示第 $i$ 栋楼的第 $j$ 层。 - $(1,1) \to (2,1) \to (3,1) \to (3,2) \to (2,2) \to (1,2) \to (1,1)$ - $(1,1) \to (3,1) \to (2,1) \to (2,2) \to (3,2) \to (1,2) \to (1,1)$ - $(1,1) \to (3,1) \to (3,2) \to (1,2) \to (2,2) \to (2,1) \to (1,1)$ - $(1,1) \to (1,2) \to (2,2) \to (3,2) \to (3,1) \to (2,1) \to (1,1)$ - $(1,1) \to (1,2) \to (3,2) \to (2,2) \to (2,1) \to (3,1) \to (1,1)$ - $(1,1) \to (2,1) \to (2,2) \to (1,2) \to (3,2) \to (3,1) \to (1,1)$ 由 ChatGPT 4.1 翻译