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)$. [Image] These are the examples of valid and invalid grid when $n=k=2$. 


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


-----Examples-----
Input
2 2

Output
7

Input
123 456789

Output
689974806



-----Note-----

In the first example, following $7$ cases are possible. [Image] 

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

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
def Solve(n, k):
	mod = 10 ** 9 + 7
	max_n = 10 ** 4
	fac = [1] + [0] * max_n
	fac_i = [1] + [0] * max_n
	for i in range(1, n + 1):
		fac[i] = fac[i - 1] * i % mod
		fac_i[i] = fac_i[i - 1] * pow(i, mod - 2, mod) % mod

	def mod_nCr(n, r):
		if n == 0 and r == 0:
			return 1
		if n < r or n < 0:
			return 0
		temp = fac_i[n - r] * fac_i[r] % mod
		return temp * fac[n] % mod
	ans = 0
	for i in range(n + 1):
		base = pow(k, n - i, mod) * pow(k - 1, i, mod) - pow(k - 1, n, mod) + mod
		base % mod
		val = pow(-1, i) * mod_nCr(n, i) * pow(base, n, mod)
		ans += val
		ans %= mod
	return ans
(n, k) = [int(item) for item in input().split()]
mod = 10 ** 9 + 7
max_n = 10 ** 4
fac = [1] + [0] * max_n
fac_i = [1] + [0] * max_n
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % mod
	fac_i[i] = fac_i[i - 1] * pow(i, mod - 2, mod) % mod

def mod_nCr(n, r):
	if n == 0 and r == 0:
		return 1
	if n < r or n < 0:
		return 0
	temp = fac_i[n - r] * fac_i[r] % mod
	return temp * fac[n] % mod
ans = 0
for i in range(n + 1):
	base = pow(k, n - i, mod) * pow(k - 1, i, mod) - pow(k - 1, n, mod) + mod
	base % mod
	val = pow(-1, i) * mod_nCr(n, i) * pow(base, n, mod)
	ans += val
	ans %= mod
print(ans)


(n, k) = list(map(int, input().split()))
M = 10 ** 9 + 7

def binom(a, b):
	num = 1
	for i in range(a, a - b, -1):
		num = num * i % M
	denom = 1
	for i in range(1, b + 1):
		denom = denom * i % M
	return num * pow(denom, M - 2, M)
binomMem = [0] * (251 * 300)
for i in range(n + 1):
	for j in range(i + 1):
		binomMem[300 * i + j] = binom(i, j) * pow(k - 1, i - j, M) % M
count = [0] * (n + 1)
count[0] = 1
for _ in range(n):
	new = [0] * (n + 1)
	for i in range(n + 1):
		curr = count[i]
		new[i] -= pow(k - 1, n, M) * curr
		curr *= pow(k, i, M)
		curr %= M
		for add in range(n + 1 - i):
			new[i + add] += curr * binomMem[300 * (n - i) + add]
			new[i + add] %= M
	count = new
print(count[n])


def main():
	(n, k) = list(map(int, input().split()))
	MOD = 10 ** 9 + 7
	Comb = [None] * (n + 1)
	dp = [[None] * (n + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		Comb[i] = [1] + [(Comb[i - 1][j - 1] + Comb[i - 1][j]) % MOD for j in range(1, i)] + [1]

	def powgen(base):
		cur = 1
		while True:
			yield cur
			cur = cur * base % MOD
	(gen, gen_1) = (powgen(k), powgen(k - 1))
	kpower = [next(gen) for i in range(n + 1)]
	k1power = [next(gen_1) for i in range(n + 1)]
	dp[1][0] = (kpower[n] - k1power[n] + MOD) % MOD
	for i in range(1, n + 1):
		dp[1][i] = kpower[n - i]
	for r in range(2, n + 1):
		dp[r] = [(dp[r - 1][c] * k1power[c] * (kpower[n - c] - k1power[n - c]) + kpower[n - c] * sum([dp[r - 1][c - i] * Comb[c][i] * k1power[c - i] for i in range(1, c + 1)])) % MOD for c in range(n + 1)]
	return dp[n][n]
print(main())


fa = [1]
m = 251
P = 10 ** 9 + 7
for i in range(1, m + 1):
	fa.append(fa[-1] * i % P)
fainv = [pow(fa[m], P - 2, P)]
for i in range(1, m + 1)[::-1]:
	fainv.append(fainv[-1] * i % P)
fainv = fainv[::-1]

def C(a, b):
	return fa[a] * fainv[a - b] * fainv[b] % P
(N, K) = map(int, input().split())
poK = [1]
for i in range(251):
	poK.append(poK[-1] * K % P)
poK1 = [1]
for i in range(251):
	poK1.append(poK1[-1] * (K - 1) % P)
dpC = [[C(i, j) for j in range(i + 1)] for i in range(N + 1)]
dpCpoK = [[C(i, j) * poK[j] % P for j in range(i + 1)] for i in range(N + 1)]
DP = [[0] * (N + 1) for _ in range(N + 1)]
DP[0][0] = 1
for i in range(1, N + 1):
	for j in range(1, N + 1):
		for k in range(j + 1):
			if k < j:
				DP[i][j] = (DP[i][j] + DP[i - 1][k] * dpCpoK[j][k]) % P
			else:
				DP[i][j] = (DP[i][j] + DP[i - 1][k] * dpC[j][k] % P * (poK[k] - poK1[k])) % P
	for j in range(1, N + 1):
		DP[i][j] = DP[i][j] * poK1[N - j] % P
print(DP[N][N])


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
mod = 10 ** 9 + 7
FACT = [1]
for i in range(1, 250 + 1):
	FACT.append(FACT[-1] * i % mod)
FACT_INV = [pow(FACT[-1], mod - 2, mod)]
for i in range(250, 0, -1):
	FACT_INV.append(FACT_INV[-1] * i % mod)
FACT_INV.reverse()

def Combi(a, b):
	if 0 <= b <= a:
		return FACT[a] * FACT_INV[b] % mod * FACT_INV[a - b] % mod
	else:
		return 0
COMBI = [[0] * 251 for i in range(251)]
for a in range(251):
	for b in range(a + 1):
		COMBI[a][b] = Combi(a, b)
POW_K = [1]
POW_K1 = [1]
for i in range(n + 1):
	POW_K.append(POW_K[-1] * k % mod)
	POW_K1.append(POW_K1[-1] * (k - 1) % mod)
DP = [0] * (n + 1)
DP[0] = 1
PLUS = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n + 1):
	for j in range(n + 1):
		if i == j:
			PLUS[i][j] = (POW_K[i] * COMBI[n - i][j - i] * POW_K1[n - j] - POW_K1[n]) % mod
		else:
			PLUS[i][j] = POW_K[i] * COMBI[n - i][j - i] * POW_K1[n - j] % mod
for yoko in range(n):
	NDP = [0] * (n + 1)
	for i in range(n + 1):
		if DP[i] == 0:
			continue
		for j in range(max(1, i), n + 1):
			NDP[j] = (NDP[j] + PLUS[i][j] * DP[i]) % mod
	DP = NDP
print(DP[-1])


def main():
	MOD = 10 ** 9 + 7
	(n, k) = [int(c) for c in input().split()]
	f = [[None for j in range(n + 1)] for i in range(n + 1)]
	if k == 1:
		return 1
	nCr = [[0 for j in range(i + 1)] for i in range(n + 1)]
	nCr[0][0] = 1
	for i in range(1, n + 1):
		nCr[i] = [1] + [(nCr[i - 1][j] + nCr[i - 1][j - 1]) % MOD for j in range(1, i)] + [1]

	def powgen(base):
		this = 1
		while True:
			yield this
			this = this * base % MOD
	(kpowgen, k1powgen) = (powgen(k), powgen(k - 1))
	kpower = [next(kpowgen) for i in range(n + 1)]
	k1power = [next(k1powgen) for i in range(n + 1)]
	for r in range(1, n + 1):
		f[r][0] = pow(kpower[n] - k1power[n], r, MOD)
	for c in range(1, n + 1):
		f[1][c] = kpower[n - c]
	for r in range(2, n + 1):
		f[r] = [f[r][0]]
		f[r] += [((kpower[n - c] - k1power[n - c]) * k1power[c] * f[r - 1][c] + kpower[n - c] * sum((k1power[c - c0] * nCr[c][c0] * f[r - 1][c - c0] for c0 in range(1, c + 1)))) % MOD for c in range(1, n + 1)]
	return f[n][n]
print(main())


(n, k) = [int(item) for item in input().split()]
MOD = 10 ** 9 + 7
MAX_N = 10 ** 4
fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % MOD
	fac_inv[i] = fac_inv[i - 1] * pow(i, MOD - 2, MOD) % MOD

def mod_nCr(n, r):
	if n == 0 and r == 0:
		return 1
	if n < r or n < 0:
		return 0
	tmp = fac_inv[n - r] * fac_inv[r] % MOD
	return tmp * fac[n] % MOD
ans = 0
for i in range(n + 1):
	base = pow(k, n - i, MOD) * pow(k - 1, i, MOD) - pow(k - 1, n, MOD) + MOD
	base % MOD
	val = pow(-1, i) * mod_nCr(n, i) * pow(base, n, MOD)
	ans += val
	ans %= MOD
print(ans)


MOD = int(1000000000.0 + 7)

def mult(l, r):
	return l * r % MOD

def fast_exp(b, e):
	if e == 0:
		return 1
	if e % 2 == 1:
		return mult(b, fast_exp(b, e - 1))
	else:
		b2 = fast_exp(b, e // 2)
		return mult(b2, b2)
[n, k] = [int(s) for s in input().split(' ')]
fact = (n + 1) * [1]
for i in range(1, n + 1):
	fact[i] = mult(i, fact[i - 1])
ifact = (n + 1) * [1]
ifact[n] = fast_exp(fact[n], MOD - 2)
for i in reversed(range(1, n)):
	ifact[i] = mult(i + 1, ifact[i + 1])

def binom(N, K):
	return mult(mult(fact[N], ifact[K]), ifact[N - K])

def get(i, j):
	X = i * j
	Y = (n - i) * j
	Z = (n - j) * i
	tot = X + Y + Z
	ans = 0
	if (i + j) % 2 == 0:
		ans = 1
	else:
		ans = MOD - 1
	ans = mult(ans, binom(n, j))
	ans = mult(ans, binom(n, i))
	ans = mult(ans, fast_exp(k, n * n - tot))
	ans = mult(ans, fast_exp(k - 1, tot))
	return ans
ans = 0
for i in range(0, n + 1):
	for j in range(0, n + 1):
		ans = (ans + get(i, j)) % MOD
print(ans)