Another Filling the Grid

题意翻译

给定一个 $n\times n$ 的矩阵,用 $1\sim k$ 的数填充,每行每列最小值均为 $1$,问有多少填法,对 $10^9+7$ 取模。 $1\le n\le 250,1\le k\le 10^9$。

题目描述

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) $ . ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1228E/461043b230da4734e02a378fa88336fd5a76ad41.png) 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) $ .

输入输出样例

输入样例 #1

2 2

输出样例 #1

7

输入样例 #2

123 456789

输出样例 #2

689974806

说明

In the first example, following $ 7 $ cases are possible. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1228E/50e0a56b2ebcb373865c65f252219c6e6fb65791.png)In the second example, make sure you print the answer modulo $ (10^{9} + 7) $ .