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 Codeforces1151F {

	public static void main(String[] args) throws IOException {
		int P = 1000000007;
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		//count number of zeroes in array
		int r = 0;
		for (int i = 0; i < n; i++) {
			r += (1-a[i]);
		}
		//count number of ones in first r things
		int s = 0;
		for (int i = 0; i < r; i++) {
			s += a[i];
		}
		
		if (r > (n/2)) {
			r = n-r;
		}
		
		int nC2Inv = (n*(n-1))/2;
		nC2Inv = inverse(nC2Inv, P);
		
		//create matrix
		int[][] matrix = new int[r+1][r+1];
		for (int i = 0; i <= r; i++) {
			matrix[i][i] = 1;
			if (i > 0) {
				matrix[i][i-1] = multiply(i*i, nC2Inv, P);
				matrix[i][i] = (matrix[i][i] + P - matrix[i][i-1])%P;
			}
			if (i < r) {
				matrix[i][i+1] = multiply(((r-i)*(n-r-i)), nC2Inv, P);
				matrix[i][i] = (matrix[i][i] + P - matrix[i][i+1])%P;
			}
		}
		
		//matrix power k
		int[][] ans = power(matrix, k, P);
		System.out.println(ans[s][0]);
	}
	
	public static int[][] power(int[][] a, int k, int N) {
		if (k == 1) {
			return a;
		}
		else {
			int[][] prod = multiply(a, a, N);
			int[][] ans = power(prod, k/2, N);
			if (k%2 == 1) {
				ans = multiply(ans, a, N);
			}
			return ans;
		}
		
	}

	public static int[][] multiply (int[][] a, int[][] b, int N) {
		int n = a.length;
		int m = a[0].length;
		int p = b[0].length;
		
		int[][] ans = new int[n][p];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < p; j++) {
				for (int k = 0; k < m; k++) {
					ans[i][j] = (ans[i][j] + multiply(a[i][k], b[k][j], N))%N;
				}
			}
		}
		
		return ans;
	}
	
	public static int multiply (int a, int b, int n) {
		long ab = (long) a * (long) b;
		return ((int) (ab%n));
	}
	
	public static int inverse (int a, int n) {
		int m = n;
		int r1 = 1;
		int r2 = 0;
		int r3 = 0;
		int r4 = 1;
		while ((a > 0) && (n > 0)) {
			if (n >= a) {
				r3 -= r1*(n/a);
				r4 -= r2*(n/a);
				n = n%a;
			}
			else {
				int tmp = a;
				a = n;
				n = tmp;
				tmp = r1;
				r1 = r3;
				r3 = tmp;
				tmp = r2;
				r2 = r4;
				r4 = tmp;
			}
		}
		if (a == 0) {
			if (r3 >= 0)
				return (r3%m);
			else
				return (m+(r3%m));
		}
		else {
			if (r1 >= 0)
				return (r1%m);
			else
				return (m+(r1%m));
		}

	}

}
