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 F553 {
    public static void main(String[] args) throws Exception {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt();
        long k = sc.nextLong();
        int [] arr = new int[n];
        int a = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (arr[i] == 0) a++;
        }
        int b = n - a;
        initFac(104);
        dimension = a + 1;
        memo = new long[maxPow][dimension][dimension];
        long [][] matrix = new long[dimension][dimension];
        for (int i = 0; i < dimension; i++) {
            // dp[i] = ...
            long choose = (n * (n - 1)) / 2;
            if (i > 0)
                matrix[i][i - 1] = ((i * (b - a + i)) * inv(choose)) % mod;
            if (i < a)
                matrix[i][i + 1] = ((a - i) * (a - i) * inv(choose)) % mod;
            long num = choose - (i * (b - a + i) + (a - i) * (a - i));
            matrix[i][i] = (num * inv(choose)) % mod;
        }
        powers(matrix);
        int start = 0;
        for (int i = 0; i < a; i++) {
            if (arr[i] == 0) start++;
        }
        long [][] res = exp(matrix, k);
        long [] vector = new long[dimension];
        vector[a] = 1;
        vector = transform(vector, res);
        out.println(vector[start]);
        out.close();
    }

    static long mod = (long) 1e9 + 7; static long [][][] memo; static int maxPow = 30; static int dimension;

    static long [][] multiply(long [][] a, long [][] b) throws Exception {
        if (a[0].length != b.length) {
            throw new Exception("Matrices are not compatible.");
        }
        long [][] ret = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                long product = 0;
                for (int k = 0; k < a.length; k++) {
                    product = (product + a[i][k] * b[k][j]) % mod;
                }
                ret[i][j] = product;
            }
        }
        return ret;
    }

    static long[][] exp(long [][] a, long pow) throws Exception {
        long [][] ret = getIdentity(dimension);
        for (int i = 0; i < maxPow; i++) {
            if (((pow) & (1L << i)) >> i == 1) {
                ret = multiply(ret, memo[i]);
            }
        }
        return ret;
    }

    static void powers(long [][] a) throws Exception {
        for (int i = 0; i < maxPow; i++) {
            memo[i] = a;
            a = square(a);
        }
    }

    static long [][] square(long [][] a) throws Exception {
        return multiply(a, a);
    }

    static long [][] getIdentity(int dimension) {
        long [][] I = new long[dimension][dimension];
        for (int i = 0; i < dimension; i++) {
            I[i][i] = 1;
        }
        return I;
    }

    static long[] transform(long [] vector, long [][] matrix) throws Exception {
        if (vector.length != matrix[0].length) {
            throw new Exception("Dimensions are not compatible.");
        }
        long [] res = new long[vector.length];
        for (int i = 0; i < vector.length; i++) {
            long sum = 0;
            for (int j = 0; j < vector.length; j++) {
                sum = (sum + matrix[i][j] * vector[j]) % mod;
            }
            res[i] = sum;
        }
        return res;
    }


    static void sort(int[] a) {
        ArrayList<Integer> q = new ArrayList<>();
        for (int i : a) q.add(i);
        Collections.sort(q);
        for (int i = 0; i < a.length; i++) a[i] = q.get(i);
    }

    static void sort(long[] a) {
        ArrayList<Long> q = new ArrayList<>();
        for (long i : a) q.add(i);
        Collections.sort(q);
        for (int i = 0; i < a.length; i++) a[i] = q.get(i);
    }

    static long[] fac;

    static void initFac(long n) {
        fac = new long[(int)n + 1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = (fac[i - 1]  * i) % mod;
        }
    }



    static long nck(int n, int k) {
        if (n < k)
            return 0;
        long den = inv((int) (fac[k] * fac[n - k] % mod));
        return fac[n] * den % mod;
    }

    static long pow(long b, long e) {
        long ans = 1;
        while (e > 0) {
            if (e % 2 == 1)
                ans = ans * b % mod;
            e >>= 1;
            b = b * b % mod;
        }
        return ans;
    }

    static long inv(long x) {
        return pow(x, mod - 2);
    }


    //-----------MyScanner class for faster input----------
    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;
        }


    }

}