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

Difficulty: interview

Starter code:

Solutions:
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 = list(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)
 
print(DP[-1])

def main():

    # Basic construction
    MOD = 10**9 + 7 # MOD
    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 # Edge case

    # nCr
    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]

    # k^i, (k-1)^i
    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)]
    
    # Edge DP
    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]

    # DP
    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())

MOD = int(1e9+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)

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
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    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
total = pow(k, n*n, MOD)
for i in range(n+1):
    for j in range(n+1):
        not_one = (n - i + n - j) * n - ((n - i) * (n - j))
        free = n * n - not_one
        val = pow(-1, i+j) * mod_nCr(n, i) * mod_nCr(n, j) * pow(k-1, not_one, MOD) * pow(k, free, MOD)
        ans += val
        ans %= MOD

print(ans)

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)


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): # row remaining
        # c means col incompleted
        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)]
    # input 250 1000000000
    return dp[n][n]

print(main())





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): # row remaining
        # c means col incompleted
        for c in range(n+1): 
            dp[r][c] = (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
            
    # input 250 1000000000
    return dp[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)