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.
import java.io.*;
import java.util.*;

public class Main implements Runnable{
    public static void main(String[] args){
        //new Thread(null,new Main(),"Thread-1",1024*1024*10).start();
        new Main().run();
    }
    int[]a;
    int tot=0;
    long[]inv;
    int mod=1000000007;
    private void solve() throws Exception {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int n=in.nextInt(),k=in.nextInt();
        a=new int[n];
        inv=getInvs(10000,mod);
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
            if(a[i]==1)tot++;
        }
        int where=0;
        for(int i=0;i<n-tot;i++){
            if(a[i]==1)where++;
        }
        int len=Math.min(n-tot,tot);
        long[][]matrix=new long[len+1][len+1];
        long all=(long)n*(n-1)*inv[2]%mod;
        long invall=inv[(int)all];
        for(int i=0;i<=len;i++){
            long cnt=0;
            if(i>0){
                matrix[i-1][i]=i*i*invall%mod;
                cnt+=i*i;
            }
            if(i<len){
                matrix[i+1][i]=(tot-i)*(n-tot-i)*invall%mod;
                cnt+=(tot-i)*(n-tot-i);
            }
            matrix[i][i]=((all-cnt)%mod+mod)%mod*invall%mod;
        }
        long[][]ans=pow(matrix,k);
        out.println(ans[0][where]);
        out.flush();
    }
    public long[][]pow(long[][]a,int b){
        long[][]ans=new long[a.length][a.length];
        for(int i=0;i<a.length;i++)ans[i][i]=1;
        while(b>0){
            if((b&1)==1)ans=modMul(ans,a);
            a=modMul(a,a);
            b>>=1;
        }
        return ans;
    }
    public long[][] modMul(long[][]a,long[][]b){
        int row=a.length,column=b[0].length;
        int len=b.length;
        long[][] ans=new long[row][column];
        for(int i=0;i<row;i++){
            for(int j=0;j<len;j++){
                //if(a[i][j]==0)continue;//稀疏矩阵优化
                for(int k=0;k<column;k++){
                    ans[i][k]+=a[i][j]*b[j][k]%mod;
                    ans[i][k]%=mod;
                }
            }
        }
        return ans;
    }
    public static long[] getInvs(int n,int mod){
        long[]inv=new long[n+1];
        inv[1]=1;
        for(int i=2;i<inv.length;i++)
            inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        return inv;
    }
    @Override
    public void run() {
        try {
            solve();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
    class InputReader{
        StreamTokenizer tokenizer;
        public InputReader(InputStream stream){
            tokenizer=new StreamTokenizer(new BufferedReader(new InputStreamReader(stream)));
            tokenizer.ordinaryChars(33,126);
            tokenizer.wordChars(33,126);
        }
        public String next() throws IOException {
            tokenizer.nextToken();
            return tokenizer.sval;
        }
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
        public boolean hasNext() throws IOException {
            int res=tokenizer.nextToken();
            tokenizer.pushBack();
            return res!=tokenizer.TT_EOF;
        }
    }
}