#P1228E. Another Filling the Grid
Another Filling the Grid
No submission language available for this problem.
Description
You have $n \times n$ square grid and an integer $k$. Put an integer in each cell while satisfying the conditions below.
- All numbers in the grid should be between $1$ and $k$ inclusive.
- Minimum number of the $i$-th row is $1$ ($1 \le i \le n$).
- Minimum number of the $j$-th column is $1$ ($1 \le j \le n$).
Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo $(10^{9} + 7)$.
The only line contains two integers $n$ and $k$ ($1 \le n \le 250$, $1 \le k \le 10^{9}$).
Print the answer modulo $(10^{9} + 7)$.
Input
The only line contains two integers $n$ and $k$ ($1 \le n \le 250$, $1 \le k \le 10^{9}$).
Output
Print the answer modulo $(10^{9} + 7)$.
Samples
2 2
7
123 456789
689974806
Note
In the first example, following $7$ cases are possible.
In the second example, make sure you print the answer modulo $(10^{9} + 7)$.