Description

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 \(\frac{P}{Q}\), where \(P\) and \(Q\) are coprime integers and \(Q \not\equiv 0\ (\text{mod}\ 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, \dots ,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}\ (\text{mod}\ 10^9+7)\), where \(P\) and \(Q\) are defined above.

Examples

Input

3 20 1 0

Output

333333336

Input

5 11 1 1 0 0

Output

0

Input

6 41 0 0 1 1 0

Output

968493834

Solution

设\(n\)个数中\(0\)的个数为\(a\)，\(1\)的个数为\(b\)，用\(d_{i, j}\)表示完成\(i\)次操作后，能使前\(a\)个数字中有\(j\)个\(1\)的操作序列的数量，设原数组中，前\(a\)个数字里有\(c\)个\(0\)，则我们将\(d_{0,c}\)初始化为1，问题的答案为\(\displaystyle\frac{d_{k, a}}{\sum_{i=0}^{a}d_{k, i}}\)

现在考虑转移，\(d_{i, j}\)可以从\(d_{i - 1, j - 1}\)、\(d_{i-1,j}\)和\(d_{i-1,j +1}\)转移而来

• \(d_{i-1,j}\)：或者前\(a\)个数中的两个交换，或者后\(b\)个数中的两个交换，或者前\(a\)个数中的\(0\)与后\(b\)个数中的\(0\)交换，或者前\(a\)个数中的\(1\)与后\(b\)个数中的\(1\)交换
• \(d_{i-1,j-1}\)：前\(a\)个数中的\(1\)与后\(b\)个数中的\(0\)交换
• \(d_{i-1,j+1}\)：前\(a\)个数中的\(0\)与后\(b\)个数中的\(1\)交换

所以得到转移函数：

\[ \begin{aligned} d_{i,j} = &d_{i-1,j} * \left(\text{C}(a,2) + \text{C}(b,2) + j*(a-j) + (a-j)*(b-a+j)\right)\\ &d_{i-1,j-1} * \left(a-j+1\right)*(a-j+1)\\ &d_{i-1,j+1} *(j+1)*(b-a+j+1) \end{aligned} \]

由于\(d_{i,*}\)只跟\(d_{i-1,*}\)有关，且转移函数中的系数与\(i\)无关，所以可以用矩阵快速幂来求\(d_{k,*}\)，复杂度\(O(n^3 \log k)\)

#include 
    
     using namespace std;using ll = long long;const ll mod = 1e9 + 7;struct SquareMatrix {  SquareMatrix(int _n) : n(_n) {    data.assign(_n, vector
     
      (_n, 0));  }  vector
      
        &operator[](int i) {    return data[i];  }  const vector
       
         &operator[](int i) const {    return data[i];  }  SquareMatrix operator*(const SquareMatrix &other) const {    assert(n == other.n);    SquareMatrix ret(n);    for (int i = 0; i < n; ++i) {      for (int j = 0; j < n; ++j) {        for (int k = 0; k < n; ++k) {          ret[i][j] = (ret[i][j] + data[i][k] * other[k][j]) % mod;        }      }    }    return ret;  }  vector
        
         
          > data; int n;};SquareMatrix quickpower(SquareMatrix m, int p) { int n = m.n; SquareMatrix ret(n); for (int i = 0; i < n; ++i) ret[i][i] = 1; while (p) { if (p & 1) { ret = ret * m; } m = m * m; p >>= 1; } return ret;}ll quickpower(ll x, int p) { ll ret = 1; while (p) { if (p & 1) ret = (ret * x) % mod; x = (x * x) % mod; p >>= 1; } return ret;}int main() { int n, k; scanf("%d%d", &n, &k); vector
          
            a(n); int x = 0, y = 0, z = 0; for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); x += a[i] == 0; } y = n - x; for (int i = 0; i < x; ++i) z += a[i] == 0; if (x > y) { // 如果0的个数大于1的个数，可以反向处理数组 swap(x, y); z = 0; for (int i = n - 1; i >= n - x; --i) z += a[i] == 1; } SquareMatrix m(x + 1); for (int i = 0; i <= x; ++i) { m[i][i] = x * (x - 1) / 2 + y * (y - 1) / 2 + i * (x - i) + (x - i) * (y - x + i); if (i - 1 >= 0) m[i][i - 1] = (x - i + 1) * (x - i + 1); if (i + 1 <= x) m[i][i + 1] = (i + 1) * (y - x + i + 1); } m = quickpower(m, k); ll ans = 0; for (int i = 0; i <= x; ++i) ans = (ans + m[i][z]) % mod; ans = m[x][z] * quickpower(ans, mod - 2) % mod; printf("%I64d\n", ans); return 0;}