诅咒护符
时间限制：1秒
内存限制：256 MB
输入：标准输入
输出：标准输出
在东京都立魔法技术学校，有 $m$ 种独特的诅咒标记。为了区分，标记被赋予了从 $0$ 到 $m-1$ 的整数编号。
该校的一种物品是诅咒护符的组装。大小为 $n$ 的护符是由 $n$ 个独特的诅咒标记按一定顺序组成的序列，即一个集合 $a_1, a_2, \ldots, a_n$，其中对于所有 $i$，$0 \le a_i < m$，且所有 $a_i$ 互不相同。护符的最终强度定义为
$$f(a_1, \ldots, a_n) = \sum_{i=1}^n \operatorname{mex}(a_1, \ldots, a_i).$$
这里，数组的 $\operatorname{mex}$ 是不属于该数组的最小非负整数。
由于可以组装很多护符，老师们想知道所有可能的不同护符的总强度之和。护符 $a$ 和 $a'$ 被认为是不同的，如果存在一个下标 $1 \le i \le n$ 使得 $a_i \neq a'_i$。
你需要帮助老师们计算这个数。由于它可能非常大，输出模 $10^9+7$ 的结果。
输入数据
一行两个整数 $n$ 和 $m$ —— 护符的大小和可用标记的数量（$1 \le n \le 10^6$；$n \le m \le 10^9$）。
输出数据
一行输出答案。
评分系统
| 子任务 | 分数 | 额外限制 | 依赖子任务 | 评测方式 |
|---|---|---|---|---|
| 0 | – | 样例中的例子 | 无 | 完全 |
| 1 | $5$ | $m \le 8$ | 无 | 完全 |
| 2 | $15$ | $m \le 20$ | 1 | 完全 |
| 3 | $12$ | $m \le 300$ | 0–2 | 完全 |
| 4 | $5$ | $n \le 300$ | 0 | 完全 |
| 5 | $8$ | $m \le 2000$ | 0–3 | 完全 |
| 6 | $8$ | $n \le 2000$ | 0, 4 | 完全 |
| 7 | $15$ | $n = m$ | 无 | 完全 |
| 8 | $10$ | $m \le 10^6$ | 0–7 | 完全 |
| 9 | $22$ | — | 0–8 | 完全 |
示例
输入
2 3输出
8输入
3 5输出
102输入
100 100输出
410874080