R国の住民は、$k$ 本の通りがある都市に住んでおり、各通りには $n$ 棟の家が整然と格子状に並んでいます。当初、向かい合う家同士はすべて道路で結ばれていました。簡単に言えば、これらの家は格子状の道路でつながっています。しかし最近、市役所は資金難のため、これほど多くの道路を維持することが困難になり、道路の数をできるだけ減らさざるを得なくなりました。ただし、どの2棟の家も道路でつながっている状態を維持しなければなりません。ここで、通りにある道路も一部取り壊すことができることに注意してください。最終的に残る道路の数は $kn - 1$ 本になることは明らかです。この条件を満たす方法が全部で何通りあるか計算してください。
答えは $P = 10^9 + 7$ で割った余りを出力してください。
入力
一行に2つの整数 $k, n$ が与えられます。
出力
答えを1つの数として出力してください。
小課題
| テストケース番号 | $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$ を満たします。
入出力例
入力 1
2 2
出力 1
4