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.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static long MOD = 1000000007;

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int k = scanner.nextInt();

        final ArrayList<Integer> values = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            values.add(scanner.nextInt());
        }
        
        final int zeroCount = values.stream().filter(integer -> integer.equals(0)).mapToInt(i -> 1).sum();
        final int oneCount = n - zeroCount;
        final int size = Math.min(zeroCount, oneCount);

        long[][] table = new long[size + 1][size + 1];

        int diff = 0;
        for (int i = 0; i < n; i++) {
            if (values.get(i) == 0 && i >= zeroCount) {
                diff++;
            }
        }


        final int allPosible = (n * (n - 1)) / 2;
        final long allPosibleInverse = binPow(allPosible, MOD - 2);
        for (int i = 0; i < size + 1; i++) {
            for (int j = 0; j < size + 1; j++) {

                if (i - j == 1) {
                    table[i][j] = i * i * allPosibleInverse;
                }

                if (i - j == 0) {
                    table[i][j] = (allPosible - i * i - (zeroCount - i) * (oneCount - i)) * allPosibleInverse;
                }

                if (i - j == -1) {
                    table[i][j] = (zeroCount - i) * (oneCount - i) * allPosibleInverse;
                }
                table[i][j] = table[i][j] % MOD;
            }
        }

        table = binPow(table, k);

//        for (long[] longs : table) {
//            for (long value : longs) {
//                System.out.printf("%10d", value);
//            }
//            System.out.println();
//        }

        System.out.println(table[diff][0]);
    }

    private static long binPow(long n, long count) {
        if (count == 0) {
            return 1L;
        }

        long temp = binPow(n, count / 2);
        temp = (temp * temp) % MOD;
        if (count % 2 != 0) {
            temp = (temp * n) % MOD;
        }

        return temp % MOD;
    }

    private static long[][] binPow(long[][] table, long count) {
        if (count == 0) {
            final long[][] ans = new long[table.length][table.length];
            for (int i = 0; i < table.length; i++) {
                ans[i][i] = 1;
            }
            return ans;
        }

        long[][] temp = binPow(table, count / 2);
        temp = (mul(temp, temp));
        if (count % 2 != 0) {
            temp = mul(temp, table);
        }

        return temp;
    }

    private static long[][] mul(long[][] a, long[][] b) {
        final long[][] ans = 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++) {
                    ans[i][j] += (a[i][k] * b[k][j]) % MOD;
                    ans[i][j] = ans[i][j] % MOD;
                }
            }
        }
        return ans;
    }
}