Petar 和 Ivana 在一个漫长的冬日午后感到无聊，于是他们决定发明一个关于数字的游戏。
Petar 拿出一张纸，随机写下 $n$ 个数字。每个数字都是完全随机且独立地从 $1$ 到 $k$ 的整数中选取的。通过这种方式，Petar 创建了一个包含 $n$ 个数字的数组 $a$。
Ivana 说她特别喜欢某些数组，因为它们具有一种“隐藏的平衡”，她称这些数组为结构（structures）。如果满足以下条件，则一个数组是一个结构：
- $1$ 到 $n$ 中的每个数字在数组中恰好出现一次。
- 对于每个索引 $i$（$1 \le i \le n$），满足 $|a_i + i - n - 1| \le 1$。
Ivana 想知道 Petar 在完全随机选择数字的情况下，构建出的数组是一个结构的概率。
可以证明，答案总能表示为分数 $\frac{P}{Q}$，其中 $P$ 是整数，$Q$ 是不能被 $10^9 + 7$ 整除的正整数。在这种情况下，输出 $P \cdot Q^{-1} \pmod{10^9 + 7}$。
输入格式
第一行包含自然数 $n$ 和 $k$（$1 \le n, k \le 10^9$），即题目描述中的数字。
输出格式
输出一个整数，即题目描述中问题的答案。
数据范围
| 子任务 | 分数 | 数据范围 |
|---|---|---|
| 1 | 17 | $n, k \le 7$ |
| 2 | 23 | $n \le 7, k \le 100$ |
| 3 | 19 | $n \le 20, k \le 100$ |
| 4 | 25 | $n, k \le 10^6$ |
| 5 | 26 | 无附加限制。 |
样例
输入样例 1
2 1
输出样例 1
0
输入样例 2
2 2
输出样例 2
500000004
输入样例 3
7 94
输出样例 3
100976822
说明
样例 2 解释：Petar 可以构建的数组 $a$ 有：$(1, 1), (1, 2), (2, 1), (2, 2)$。其中是结构的数组为 $(1, 2)$ 和 $(2, 1)$。Petar 完全随机获得一个结构数组的概率为 $\frac{2}{4}$，即 $500000004 \pmod{10^9 + 7}$。