human
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 ≤ i < j ≤ 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 P/Q, where P and Q are coprime integers and Q not≡ 0~\pmod {10^9+7}.

Input

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

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 1) — the description of the array a.

Output

If the desired probability is 0, print 0, otherwise print the value P ⋅ 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 3/9=1/3.

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

=====
Write me a Python program to find the probability that after all the operations are completed, the a array will be sorted in non-decreasing order?
assistant
#Here is Python program to find the probability that after all the operations are completed, the a array will be sorted in non-decreasing order.

import sys; input=sys.stdin.readline
# print(input())
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])