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.util.*;
import java.io.*;
public class EdC {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner sc;
    public static PrintWriter out;
    static int y;
	public static void main(String[] omkar) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
 		int n = sc.nextInt();
 		long k = sc.nextLong();
 		int[] array = readArrayInt(n);
 		y = 0;
 		int initial = 0;
 		for(int j =0;j<n;j++)
 			if (array[j] == 1)
 				y++;
 		for(int j =n-y;j<n;j++)
 			if (array[j] == 1)
 				initial++;
 		long[][] matrix = new long[y+1][y+1];
 		for(int j = 0;j<=y;j++){
 			long s = n;
 			s*=(long)(n-1);
 			s/=2;
 			if (j-1 >=0){
 				matrix[j-1][j]=j;
 				matrix[j-1][j]%=mod;
 				matrix[j-1][j]*=(long)(n-2*y+j);
 				matrix[j-1][j]%=mod;
 				s-=matrix[j-1][j];
 				s%=mod;
 				s+=mod;
 				s%=mod;
 			}
 			if (j+1 <= y){
 				matrix[j+1][j]=(y-j);
 				matrix[j+1][j]%=mod;
 				matrix[j+1][j]*=(long)(y-j);
 				matrix[j+1][j]%=mod;
 				s-=matrix[j+1][j];
 				s%=mod;
 				s+=mod;
 				s%=mod;
 			}
 			matrix[j][j] = s;
 			
 		}
 		long[][] product = power(matrix, k);
 		long ans = product[y][initial];
 		ans%=mod;
 		long nC2 = n;
 		nC2*=(long)(n-1);
 		nC2/=2L;
 		long div = power(nC2, mod-2);
 		ans*=power(div, k);
 		ans%=mod;
 		
 		
 		
 		out.println(ans);
	 		
 		out.close();	
 	}
	public static long[][] mul(long[][] m1, long[][] m2){
		long[][] ans = new long[y+1][y+1];
		for(int j =0;j<=y;j++){
			for(int k = 0;k<=y;k++){
				for(int l = 0;l<=y;l++){
					ans[j][l]+=m1[j][k]*m2[k][l];
					ans[j][l]%=mod;
				}
			}
		}
		return ans;
	}
	public static long[][] power(long[][] m1, long k){

		if (k == 0){
			long[][] mst = new long[y+1][y+1];
			for(int j =0 ;j<=y;j++){
				mst[j][j] = 1L;
			}
			return mst;
		}
			
		if (k == 1)
			return m1;
		long [][]ks = power(m1, k/2L);
		if (k%2 == 0)
			return mul(ks, ks);
		else
			return mul(mul(ks, ks), m1);
	}
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<Integer>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is