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: interview

Starter code:

Solutions:
N, T = list(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)])

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #553 (Div. 2)

Problem F. Sonya and Informatics

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__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):
    # print(f'n is {n}')
    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(1e9) + 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


def __starting_point():
    STATUS = main()
    return(STATUS)


__starting_point()