机长（captain）

时间限制： 1.0 秒
空间限制： 512 MiB

问题背景

你是一名 X 星牛马航空的机长。牛马是不需要休息的！

问题描述

X 星一共有 $m$ 个城市，编号为 $1\ldots m$。X 星民航非常发达，任何两个城市之间都有航班往返直达。

你的一天被分为 $n$ 个班次，每个班次需要驾机从当前城市飞往下一个城市。公司给了你一个包含 $n$ 个城市编号的排班表 $a_1,a_2,\ldots,a_n$，表示你每天要从城市 $a_1$ 开始，依次飞往城市 $a_2,a_3,\ldots,a_n$，最后再飞回城市 $a_1$（并且立刻开始下一天同样的过程，因为牛马不需要休息）。

很明显，一个有意义的航班不可能从一个城市出发又（直接）飞回该城市，也就是你按排班表执行的任何一次飞行，起点和终点都保证是不同的城市。现在你不小心把排班表弄丢了，你想算一下符合要求的排班表总共有几种可能？两种方案不同当且仅当存在某个 $a_i$ 不相同。

输入格式

从文件 captain.in 中读取数据。

一行 2 个正整数 $n,m$。

输出格式

输出到文件 captain.out。

输出一个整数表示答案。由于方案数可能很多，只要输出模 $10^9+7$ 的余数。

输入输出样例 1

4 3

18

样例 1 说明

所有合法的方案为：1212，1213，1232，1312，1313，1323，2121，2123，2131，2313，2321，2323，3121，3131，3132，3212，3231，3232。

输入输出样例 2

100 100

689027272

样例 2 说明

将 $n=100,m=100$ 代入计算，所有合法闭合排班表的数量模 $10^9+7$ 等于 689027272。

数据规模与约定

• 对于 $10\%$ 的数据，$n,m\leq 5$。
• 对于另外 $10\%$ 的数据，$n=8,m\leq 8$。
• 对于另外 $15\%$ 的数据，$n=10,m\leq 10$。
• 对于另外 $5\%$ 的数据，$m=2$。
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$，$2\leq m\leq 10^9$。

文件读写说明

使用 C++ 标准输入输出时，可以在程序开头加入：

freopen("captain.in", "r", stdin);
freopen("captain.out", "w", stdout);