The people of country R live in a city with $k$ streets, each containing $n$ houses arranged in an orderly grid. Initially, every pair of adjacent houses is connected by a road. In short, these houses are connected by a grid-like road network. However, the municipal government is currently facing a budget shortage and cannot maintain so many roads. They must reduce the number of roads as much as possible while ensuring that any two houses remain connected. Note that roads on the streets can also be partially removed. It is easy to see that exactly $kn - 1$ roads will remain. Please calculate the total number of ways to satisfy this requirement.
The answer should be taken modulo $P = 10^9 + 7$.
Input
A single line containing two integers $k$ and $n$.
Output
Output a single integer representing the answer.
Subtasks
| Test Case ID | $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$ |
For $100\%$ of the data, it is guaranteed that $2 \le k \le 6$ and $1 \le n \le 10^9$.
Examples
Input 1
2 2
Output 1
4