A girl named Sonya is studying in the scientific lyceum of the Kingdom of Kremland. The teacher of computer science (Sonya's favorite subject!) invented a task for her.

Given an array $a$ of length $n$, consisting only of the numbers $0$ and $1$, and the number $k$. Exactly $k$ times the following happens:   Two numbers $i$ and $j$ are chosen equiprobable such that ($1 \leq i < j \leq n$).  The numbers in the $i$ and $j$ positions are swapped. 

Sonya's task is to find the probability that after all the operations are completed, the $a$ array will be sorted in non-decreasing order. She turned to you for help. Help Sonya solve this problem.

It can be shown that the desired probability is either $0$ or it can be represented as $\dfrac{P}{Q}$, where $P$ and $Q$ are coprime integers and $Q \not\equiv 0~\pmod {10^9+7}$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 100, 1 \leq k \leq 10^9$) — the length of the array $a$ and the number of operations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$) — the description of the array $a$.


-----Output-----

If the desired probability is $0$, print $0$, otherwise print the value $P \cdot Q^{-1}$ $\pmod {10^9+7}$, where $P$ and $Q$ are defined above.


-----Examples-----
Input
3 2
0 1 0

Output
333333336
Input
5 1
1 1 1 0 0

Output
0
Input
6 4
1 0 0 1 1 0

Output
968493834


-----Note-----

In the first example, all possible variants of the final array $a$, after applying exactly two operations: $(0, 1, 0)$, $(0, 0, 1)$, $(1, 0, 0)$, $(1, 0, 0)$, $(0, 1, 0)$, $(0, 0, 1)$, $(0, 0, 1)$, $(1, 0, 0)$, $(0, 1, 0)$. Therefore, the answer is $\dfrac{3}{9}=\dfrac{1}{3}$.

In the second example, the array will not be sorted in non-decreasing order after one operation, therefore the answer is $0$.

Difficulty: HARD
Tags: Matrices

Combinatorics

Dynamic programming

Probability
Skill types: Dynamic programming

Starter code:

Solutions:
__version__ = '1.8'
__date__ = '2019-04-21'
import sys

def binom_dp():
	dp = [[-1 for j in range(110)] for i in range(110)]

	def calculate(n, k):
		if n < k:
			return 0
		if n == k or k == 0:
			return 1
		if dp[n][k] > 0:
			return dp[n][k]
		else:
			dp[n][k] = calculate(n - 1, k - 1) + calculate(n - 1, k)
		return dp[n][k]
	return calculate

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def multiply(A, B, mod):
	if not hasattr(B[0], '__len__'):
		C = [sum((aij * B[j] % mod for (j, aij) in enumerate(ai))) for ai in A]
	else:
		C = [[0 for col in range(len(B[0]))] for row in range(len(A))]
		len_A = len(A)
		len_B = len(B)
		for row in range(len_A):
			if sum(A[row]) == 0:
				continue
			for col in range(len_B):
				C[row][col] = sum((A[row][k] * B[k][col] for k in range(len_B))) % mod
	return C

def memoize(func):
	memo = {}

	def wrapper(*args):
		(M, n, mod) = args
		if n not in memo:
			memo[n] = func(M, n, mod)
		return memo[n]
	return wrapper

@memoize
def matrix_pow(M, n, mod):
	if n == 2:
		return multiply(M, M, mod)
	if n == 1:
		return M
	sub_M = matrix_pow(M, n // 2, mod)
	if n % 2 == 0:
		return multiply(sub_M, sub_M, mod)
	return multiply(sub_M, matrix_pow(M, n - n // 2, mod), mod)

def solve(n, k, a, binom, mod):
	ones = sum(a)
	zeros = n - ones
	M = [[0 for col in range(zeros + 1)] for row in range(zeros + 1)]
	for row in range(max(0, zeros - ones), zeros + 1):
		pre_zeros = row
		pre_ones = zeros - pre_zeros
		post_zeros = pre_ones
		post_ones = ones - pre_ones
		M[row][row] = pre_ones * post_ones + pre_zeros * post_zeros + binom(zeros, 2) + binom(ones, 2)
		if row > max(0, zeros - ones):
			M[row - 1][row] = pre_zeros * post_ones
		if row < zeros:
			M[row + 1][row] = post_zeros * pre_ones
	M = [matrix_pow(M, k, mod)[-1]]
	b = [0] * (zeros + 1)
	b[zeros - sum(a[:zeros])] = 1
	C = multiply(M, b, mod)
	return C[-1]

def main(argv=None):
	mod = int(1000000000.0) + 7
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	binom = binom_dp()
	P = solve(n, k, a, binom, mod)
	if P == 0:
		print(0)
	else:
		Q = pow(binom(n, 2), k, mod)
		print(P * modinv(Q, mod) % mod)
	return 0
STATUS = main()
sys.exit(STATUS)


(N, T) = map(int, input().split())
A = [int(a) for a in input().split()]
if sum(A) > N // 2:
	A = [1 - a for a in A][::-1]
K = sum(A)
S = sum(A[-K:])
M = K + 1
P = 10 ** 9 + 7
inv = pow(N * (N - 1) // 2, P - 2, P)
X = [[0] * M for _ in range(M)]
for i in range(M):
	if i > 0:
		X[i - 1][i] = (K - i + 1) ** 2 * inv % P
	if i < M - 1:
		X[i + 1][i] = (N - 2 * K + i + 1) * (i + 1) * inv % P
	X[i][i] = (1 - (K - i) ** 2 * inv - (N - 2 * K + i) * i * inv) % P

def ddd(n):
	for i in range(1, 100):
		if n * i % P < 100:
			return (n * i % P, i)
	return (-1, -1)

def poww(MM, n):
	if n == 1:
		return MM
	if n % 2:
		return mult(poww(MM, n - 1), MM)
	return poww(mult(MM, MM), n // 2)

def mult(M1, M2):
	Y = [[0] * M for _ in range(M)]
	for i in range(M):
		for j in range(M):
			for k in range(M):
				Y[i][j] += M1[i][k] * M2[k][j]
				Y[i][j] %= P
	return Y
X = poww(X, T)
print(X[S][K])


M = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
(z, o) = (a.count(0), a.count(1))
d = pow(n * (n - 1) // 2, M - 2, M)
if z > o:
	(o, z) = (z, o)
	a = [1 - x for x in a][::-1]
res = [[0] * (z + 1) for i in range(z + 1)]
tf = [[0] * (z + 1) for i in range(z + 1)]
for i in range(z + 1):
	res[i][i] = 1
	tf[i][i] = (z * (z - 1) // 2 + o * (o - 1) // 2 + i * (z - i) + (z - i) * (o - z + i)) * d % M
	if i < z:
		tf[i + 1][i] = (z - i) * (z - i) * d % M
	if i:
		tf[i - 1][i] = i * (o - z + i) * d % M

def mul(a, b):
	t = [[0] * (z + 1) for i in range(z + 1)]
	for i in range(z + 1):
		for k in range(z + 1):
			for j in range(z + 1):
				t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % M
	return t
while k:
	if k & 1:
		res = mul(res, tf)
	tf = mul(tf, tf)
	k >>= 1
print(res[-1][a[:z].count(0)])