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.
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const long long N = 105;
long long m;
struct node {
  long long data[N][N];
  node operator*(node b) {
    node t;
    for (long long i = 0; i <= m; i++) {
      for (long long j = 0; j <= m; j++) {
        t.data[i][j] = 0;
      }
    }
    for (long long i = 0; i <= m; i++) {
      for (long long j = 0; j <= m; j++) {
        for (long long k = 0; k <= m; k++) {
          t.data[i][j] = (t.data[i][j] + data[i][k] * b.data[k][j] % mod) % mod;
        }
      }
    }
    return t;
  }
};
inline long long ksm(long long a, long long b) {
  long long ret = 1;
  while (b) {
    if (b & 1) ret = ret * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return ret;
}
long long n, k, t, a[N];
inline long long f1(long long x) {
  return (x * (n - 2 * m + x) % mod + mod) % mod;
}
inline long long f3(long long x) {
  return ((m - x) * (m - x) % mod + mod) % mod;
}
inline long long f2(long long x) {
  return ((n * (n - 1) / 2 - f1(x) - f3(x)) % mod + mod) % mod;
}
node ma, ans;
signed main() {
  scanf("%lld%lld", &n, &k);
  for (long long i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    if (!a[i]) m++;
  }
  for (long long i = 1; i <= m; i++)
    if (!a[i]) t++;
  for (long long i = 0; i <= m; i++) {
    if (i != 0) ma.data[i - 1][i] = f1(i);
    ma.data[i][i] = f2(i);
    if (i != m) ma.data[i + 1][i] = f3(i);
  }
  for (long long i = 0; i <= m; i++) ans.data[i][i] = 1;
  while (k) {
    if (k & 1) {
      ans = ans * ma;
    }
    ma = ma * ma;
    k >>= 1;
  }
  long long total = 0;
  for (long long i = 0; i <= m; i++) {
    total = (total + ans.data[i][t]) % mod;
  }
  printf("%lld\n", ans.data[m][t] * ksm(total, mod - 2) % mod);
  return 0;
}
