Another Filling the Grid
Contest: Codeforces Round 589 (Div. 2)
Difficulty rating: 2300
Tags: combinatorics, dp, math

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

Input format:
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 250$$$, $$$1 \le k \le 10^{9}$$$).

Output format:
Print the answer modulo $$$(10^{9} + 7)$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, following $$$7$$$ cases are possible.

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

Example input:
2 2

Example output:
7

Example input:
123 456789

Example output:
689974806

Editorial:
• $$$O(n^{3})$$$ solution:Let $$$f(r, c)$$$ to be the number of filling grids of $$$r$$$ rows, $$$c$$$ incomplete columns, and $$$n-c$$$ complete columns. Incomplete columns means which doesn't contain $$$1$$$ in already filled part, and complete columns means opposite. Now you can see that the formula can be described as below;  $$$f(r, 0) = (k^{n} - (k-1)^{n})^{r}$$$ ($$$1 \le r$$$), because we don't have to care about minimum value of columns. However, there should be at least one cell which has $$$1$$$.  $$$f(1, c) = k^{n-c}$$$ ($$$1 \le c$$$), because we have to fill $$$1$$$ in all incomplete columns in that row. But, other cells are free.  $$$f(r, c) = (k^{n-c} - (k-1)^{n-c}) \cdot (k-1)^{c} \cdot f(r-1, c) + k^{n-c} \cdot \sum_{c_{0}=1}^{c} \binom{c}{c_{0}} \cdot (k-1)^{c-c0} \cdot f(r-1, c-c_{0})$$$ ($$$2 \le r$$$, $$$1 \le c$$$). Each part means number of cases when you select $$$c_{0}$$$ incomplete columns to be complete column in this row. The answer is $$$f(n, n)$$$.
• $$$f(r, 0) = (k^{n} - (k-1)^{n})^{r}$$$ ($$$1 \le r$$$), because we don't have to care about minimum value of columns. However, there should be at least one cell which has $$$1$$$.
• $$$f(1, c) = k^{n-c}$$$ ($$$1 \le c$$$), because we have to fill $$$1$$$ in all incomplete columns in that row. But, other cells are free.
• $$$f(r, c) = (k^{n-c} - (k-1)^{n-c}) \cdot (k-1)^{c} \cdot f(r-1, c) + k^{n-c} \cdot \sum_{c_{0}=1}^{c} \binom{c}{c_{0}} \cdot (k-1)^{c-c0} \cdot f(r-1, c-c_{0})$$$ ($$$2 \le r$$$, $$$1 \le c$$$). Each part means number of cases when you select $$$c_{0}$$$ incomplete columns to be complete column in this row.
• $$$O(n^{2})$$$ and $$$O(n \log n)$$$ solution:Let $$$R[i]$$$ be the restriction of the i-th row having some value <= 1 and $$$C[i]$$$ the same but for columns. We want $$$\bigcap^n_{i=1}R[i] \cap C[i]$$$.Negate that expression twice, and we'll get $$$U - \bigcup^n_{i=1}\neg R[i] \cup \neg C[i]$$$. Using inclusion-exclusion this is:$$$$$$ \sum_{i=0}^{n} \sum_{j=0}^{n} (-1)^{i+j} \cdot {n\choose j} \cdot {n\choose i} \cdot k^{n^2 - n \cdot (i+j) + i \cdot j} \cdot (k-1)^{n \cdot (i+j) - i \cdot j} $$$$$$This is enough for $$$O(n^{2} \log n)$$$ with fast exponentiation or $$$O(n^{2})$$$ precomputing the needed powers. To get $$$O(n \log n)$$$ note that we the second sum is a binomial expansion so the answer can be simplified to:$$$$$$ \sum_{i=0}^{n} (-1)^i \cdot {n\choose i} \cdot (k^{n-i} \cdot (k-1)^{i} - (k-1)^{n})^n$$$$$$