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.*;
import static java.lang.Math.*;
public class Main {
    static final long MOD = 1_000_000_007 , INF = 1_000_000_000_000_000L;
    static final int INf = 1_000_000_000;
    static FastReader reader;
    static PrintWriter writer;
    public static void main(String[] args) {
        Thread t = new Thread(null, new O(), "Integer.MAX_VALUE", 100000000);
        t.start();
    }
    static class O implements Runnable {
        public void run() {
            try {
                magic();
            }
            catch (Exception e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[1000000];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') c = read();
            boolean neg = (c == '-');
            if (neg) c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10);
            if (neg) return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null) return;
            din.close();
        }
    }

    static void magic() throws IOException {
        reader = new FastReader();
        writer = new PrintWriter(System.out, true);
        int n = reader.nextInt(), k = reader.nextInt();
        int arr[] = new int[n], curr = 0, x = 0;
        for(int i=0;i<n;++i) {
            arr[i] = reader.nextInt();
            if(arr[i]==0) {
                ++curr;
            }
        }
        for(int i=0;i<curr;++i) {
            if(arr[i]==0) {
                ++x;
            }
        }
        //writer.println("curr: "+curr+" x: "+x);
        long a[] = new long[curr+1];
        a[x] = 1;
        long M[][] = new long[curr+1][curr+1];
        for(int i=0;i<=curr;++i) {
            M[i][i] = C2(curr) + C2(n-curr) + i*(curr-i) + (curr-i) * (n-curr-(curr-i));
            if(i>0) {
                M[i-1][i] = (curr-i+1)*(curr-i+1);
            }
            if(i+1<=curr) {
                M[i+1][i] = (i+1) * (n-curr-(curr-(i+1)));
            }
        }
        M = exponentiateMatrix(M,  curr+1,k);
        long ans[] = new long[curr+1];
        for(int i=0;i<=curr;++i) {
            for(int j=0;j<=curr;++j) {
                ans[i] += a[j]*M[j][i];
                ans[i] %= MOD;
            }
        }
        long nr = ans[curr];
        long dr = 0;
        for(int i=0;i<=curr;++i) {
            dr+=ans[i];
            dr%=MOD;
        }
        writer.println((nr*modpow(dr, MOD-2))%MOD);
    }
    /**
     *
     * @param a
     * @param b
     * @param k
     * @return the product of the two (k*k) matrices a and b
     */
    static long[][] multiply(long a[][], long b[][], int k) {
        long c[][] = new long[k][k];
        for(int i=0;i<k;++i) {
            for(int j=0;j<k;++j) {
                for(int K=0;K<k;++K) {
                    c[i][j] = (c[i][j] + a[i][K]*b[K][j])%MOD;
                }
            }
        }
        return c;
    }

    /**
     *
     * @param mat
     * @param k
     * @param n
     * @return Finds the matrix: mat^n, here mat is a (k*k) matrix
     */
    static long[][] exponentiateMatrix(long mat[][], int k, long n) {
        if(n==1) {
            return mat;
        }
        if(n%2==0) {
            long half[][] = exponentiateMatrix(mat, k, n/2);
            return multiply(half, half, k);
        }
        return multiply(mat, exponentiateMatrix(mat,k, n-1), k);
    }
    static long C2(long n) {
        if(n<2) {
            return 0;
        }
        return (n*(n-1))/2;
    }
    static long modpow(long x, long y) {
        if(y==0) {
            return 1;
        }
        if((y&1)==0) {
            return modpow((x*x)%MOD, y>>1);
        }
        return (x*modpow(x, y-1))%MOD;
    }
}