← 返回题目列表

Codeforces · 1228/E

E. 另一个填充网格

中文机器翻译题面 查看原题

你有 $$$n \times n$$$ 个方形网格和一个整数 $$$k$$$。在满足以下条件的同时,在每个单元格中输入一个整数。

- 网格中的所有数字都应在 $$$1$$$ 和 $$$k$$$ 之间(含)。
- 第 $$$i$$$ 行的最小编号为 $$$1$$$ ($$$1 \le i \le n$$$)。
- 第 $$$j$$$ 列的最小编号为 $$$1$$$ ($$$1 \le j \le n$$$)。

找出在网格中放置整数的方法的数量。由于答案可能非常大,因此对 $$$(10^{9} + 7)$$$ 求模答案。

这些是当 $$$n=k=2$$$ 时有效和无效网格的示例。

输入

唯一的一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 250$$$, $$$1 \le k \le 10^{9}$$$)。

输出

打印答案模 $$$(10^{9} + 7)$$$。

示例

输入 #1

2 2

输出 #1

7

输入 #2

123 456789

输出 #2

689974806

注意

在第一个示例中,可能存在以下 $$$7$$$ 情况。

在第二个示例中,请确保打印对 $$$(10^{9} + 7)$$$ 取模的答案。