R 国的人们生活在一个有 $k$ 条街道的城市里，每条街道上坐落着 $n$ 栋房子，它们有秩序地按方阵排布。起初每两个街对面的房子也都是有道路联通的。简要说就是这些房子是以网格状道路联通的。然而最近市政府资金紧张，难以维护如此多的道路，因此不得不尽量减少道路的数量，但又要保证任意两栋房子都有道路能联通。注意，这里街上的道路也是可以拆掉一部分的。不难看出最后只会剩下 $kn - 1$ 条道路。请你计算一下，一共有多少种方案能满足这一要求？
答案对 $P = 10^9 + 7$ 取模。
输入格式
一行两个整数 $k, n$。
输出格式
输出一个数，表示答案。
样例数据
样例 1 输入
2 2
样例 1 输出
4
子任务
| 测试点编号 | $k \le $ | $n \le $ |
|---|---|---|
| $1$ | $2$ | $5$ |
| $2$ | $3$ | |
| $3$ | $2$ | $10^5$ |
| $4$ | $10^9$ | |
| $5$ | $3$ | $10^4$ |
| $6$ | $4$ | |
| $7$ | $5$ | |
| $8$ | $10^9$ | |
| $9$ | $6$ | $10^3$ |
| $10$ | $10^9$ |
对于 $100\%$ 的数据，保证 $2 \le k \le 6$, $1 \le n \le 10^9$