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.
 //package Contest553;

import java.io.PrintWriter;
import java.util.Scanner;

public class mainF {
    public static Scanner enter = new Scanner(System.in);
    public static PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] args) {
        long mod=(long)1e9+7;
        int n=enter.nextInt();
        long s=enter.nextLong();
        int[] arr=new int[n];
        int m=0;
        long CON=n*(n-1)/2;
        CON=bin_pow(CON,mod-2,mod);
        for (int i = 0; i <n ; i++) {
            arr[i]=enter.nextInt();
            m+=arr[i];
        }
        int f_k=0;
        for (int i = 0; i <n-m ; i++) {
            f_k+=arr[i];
        }
        int k=n-m;
        f_k=n-m-f_k;
        /*if(m<n-m){//Если нулей больше чем единиц
            k=m;
            f_k=n-m-f_k;
            m=n-m;
        }*/
        //f_k- кол-во нулей в первой части то есть это начальное состояние причём кол-во нулей меньше кол-ва единиц
        long[][] CM=new long[k+1][k+1];
        for (int i = Math.max(0,k-m); i <CM.length ; i++) {
            CM[i][i]=(1-(long)(i*(m-k+i)+(k-i)*(k-i))*CON);
            if(i<k) CM[i][i+1]=(long)(k-i)*(k-i)*CON;
            if(i>0)CM[i][i-1]=(long)i*(m-k+i)*CON;
        }
        MATRIX_mod(CM,mod);
        CM=bin_pow(CM,s,mod);
        System.out.println((CM[f_k][k]+mod)%mod);



    }
    public static long bin_pow(long a,long b, long mod){//a^b %mod
        long ans=1;
        while(b!=0){
            if((b&1)==1) ans*=a;
            a*=a;
            ans%=mod;
            a%=mod;
            b>>=1;
        }
        return ans;
    }

    public static long[][] bin_pow(long[][] a,long b, long mod){//a^b %mod
        long[][] ans=new long[a.length][a.length];
        for (int i = 0; i <ans.length ; i++) ans[i][i]=1;
        while(b!=0){
            if((b&1)==1) ans=MATRIX_mult(ans,a);
            a=MATRIX_mult(a,a);
            MATRIX_mod(ans,mod);
            MATRIX_mod(a,mod);
            b>>=1;
        }
        return ans;
    }
    public static long[][] MATRIX_mult(long[][] a, long[][] b) { //b не меняем a=a*b;
        long[][] c=new long[a.length][a.length];
        for (int i = 0; i <a.length ; i++) {
            for (int j = 0; j <a.length ; j++) {
                for (int k = 0; k <a.length ; k++) {
                    c[i][j]+=a[i][k]*b[k][j];
                    c[i][j]%=(long)(1e9+7);
                }
            }
        }
        return c;
    }
    public static void MATRIX_mod(long[][] a, long mod){
        for (int i = 0; i <a.length ; i++) {
            for (int j = 0; j <a.length ; j++) {
                a[i][j]%=mod;
            }
        }
    }
}
