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