30171번 - Another Filling the Grid 다국어

문제

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)$.

These are the examples of valid and invalid grid when $n=k=2$.

입력

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)$.

제한

노트

In the first example, following 7ドル$ cases are possible.

In the second example, make sure you print the answer modulo $(10^{9} + 7)$.