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$