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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        F solver = new F();
        solver.solve(1, in, out);
        out.close();
    }

    static class F {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.ni(), k = in.ni();
            int[] p = in.na(n);
            long mod = (int) 1e9 + 7;

            long cnt0 = 0, cnt1 = 0;
            for (int i = 0; i < n; i++) {
                if (p[i] == 1)
                    cnt1++;
                else
                    cnt0++;
            }

            if (cnt0 == 0 || cnt1 == 0) {
                out.println(1);
                return;
            }
            long N = (cnt0 + cnt1) * (cnt0 + cnt1 - 1) / 2 % mod;

            long[][] matrix = new long[(int) cnt0 + 1][(int) cnt0 + 1]; // m[i][j] - moving from state j to state i
            long pSame = (cnt0 * (cnt0 - 1) / 2 + cnt1 * (cnt1 - 1) / 2) % mod; // exchange withing groups
            int from = Math.max(0, (int) (cnt0 - cnt1));
            for (int i = from; i <= cnt0; i++) { // i - amount of 0 in first group
                matrix[i][i] = ((cnt0 - i) * (cnt1 - cnt0 + 2 * i) % mod + pSame) % mod;//between groups but same numbers
                if (i < cnt0) {
                    matrix[i + 1][i] = (cnt0 - i) * (cnt0 - i) % mod; // increasing amount of 0s, cnt0-i number of 0s in second group and 1s in first
                }
                if (i > from) {
                    matrix[i - 1][i] = i * (cnt1 - cnt0 + i) % mod; // decreasing amount of 0s
                }
            }
//        for (int i = 0; i <= cnt0; i++) {
//            System.out.println(Arrays.toString(matrix[i]));
//        }
            int a0 = 0;
            for (int i = 0; i < cnt0; i++) {
                if (p[i] == 0)
                    a0++;
            }
            long[] start = new long[(int) cnt0 + 1];
            start[a0] = 1; // initial state

            long[][] mPow = MatrixUtils.binPow(matrix, k, mod);
            long[] res = new long[(int) cnt0 + 1];
            MatrixUtils.multiply(mPow, start, res, mod);

            long invNK = IntegerUtils.pow(N, mod - 1 - k, mod);
            out.println(res[(int) cnt0] * invNK % mod);


        }

    }

    static class MatrixUtils {
        public static long[][] binPow(long[][] a, long k, long mod) {
            int n = a.length;
            long[][] res = new long[n][n];
            long[][] aa = new long[n][n];
            for (int i = 0; i < n; i++) {
                res[i][i] = 1;
                for (int j = 0; j < n; j++) {
                    aa[i][j] = a[i][j];
                }
            }
            long[][] nxt = new long[n][n];
            long[][] tmp;
            while (k > 0) {
                if (k % 2 == 0) {
                    multiply(aa, aa, nxt, mod);
                    tmp = aa;
                    aa = nxt;
                    nxt = tmp;
                    k /= 2;
                } else {
                    multiply(aa, res, nxt, mod);
                    tmp = nxt;
                    nxt = res;
                    res = tmp;
                    k--;
                }
            }
            return res;
        }

        public static void multiply(long[][] a, long[][] b, long[][] res, long mod) {
            for (int i = 0; i < res.length; i++) {
                for (int j = 0; j < res[i].length; j++) {
                    res[i][j] = 0;
                    for (int k = 0; k < b.length; k++) {
                        res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod;
                    }
                }
            }
        }

        public static void multiply(long[][] a, long[] b, long[] res, long mod) {
            for (int i = 0; i < res.length; i++) {
                res[i] = 0;
                for (int k = 0; k < b.length; k++) {
                    res[i] = (res[i] + a[i][k] * b[k]) % mod;
                }
            }
        }

    }

    static class IntegerUtils {
        public static long pow(long a, long p, long mod) {
            if (p == 0) {
                return 1;
            }
            long t = pow(a, p / 2, mod);

            if (p % 2 != 0) {
                return (((t * t) % mod) * a) % mod;
            } else {
                return (t * t) % mod;
            }
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

    }
}

