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.
//package com.company;
// Always comment out package when submitting.

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static class Task {
        int mod = 1000000007;
        public class Frac {
            long a, b;

            public Frac(long a, long b) {
                this.a = a % mod;
                this.b = b % mod;
            }

            public Frac add(Frac other) {
                return new Frac(a * other.b + b * other.a, b * other.b);
            }

            public Frac mult(Frac other) {
                return new Frac(a * other.a, b * other.b);
            }

            public long toVal() {
                return a * BigInteger.valueOf(b).modInverse(BigInteger.valueOf(mod)).longValue() % mod;
            }

            @Override
            public String toString() {
                return a + "/" + b;
            }
        }
        int n;
        int minP0;
        int p0, p1;
        public Frac[][] matMul(Frac[][] m1, Frac[][] m2) {
            Frac[][] f = new Frac[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    f[i][j] = new Frac(0, 1);
                }
            }
            for (int i = 0; i < n; i++) {
                for (int k = 0; k < n; k++) {
                    if (m1[i][k].a == 0) continue;
                    for (int j = 0; j < n; j++) {
                        f[i][j] = f[i][j].add(m1[i][k].mult(m2[k][j]));
                    }
                }
            }
            return f;
        }

        public Frac[][] pow(Frac[][] base, int cnt) {
            Frac[][] ret = new Frac[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    ret[i][j] = new Frac(0, 1);
                }
                ret[i][i].a = 1;
            }
            while (cnt != 0) {
                if (cnt % 2 != 0) ret = matMul(ret, base);
                base = matMul(base, base);
                cnt >>= 1;
            }
            return ret;
        }

        public Frac[][] construct() {
            Frac[][] ret = new Frac[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    ret[i][j] = new Frac(0, 1);
                }
            }
            long base = (long) (p0 + p1) * (p0 + p1 - 1) / 2;
            for (int i = minP0; i <= p0; i++) {
                int sum = 0;
                if (i > minP0) {
                    sum += i * (p1 - p0 + i);
                    ret[i - 1 - minP0][i - minP0] = new Frac(i * (p1 - p0 + i), base);
                }
                if (i + 1 - minP0 < n) {
                    sum += (p0 - i) * (p0 - i);
                    ret[i + 1 - minP0][i - minP0] = new Frac((p0 - i) * (p0 - i), base);
                }
                ret[i - minP0][i - minP0] = new Frac(base - sum, base);
            }
            return ret;
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            int k = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
                if (arr[i] == 0) {
                    p0++;
                } else {
                    p1++;
                }
            }
            if (p1 >= p0) minP0 = 0;
            else minP0 = p0 - p1;
            n = p0 - minP0 + 1;
            int cnt0 = 0;
            for (int i = 0; i < p0; i++) {
                if (arr[i] == 0) cnt0++;
            }
            Frac[][] base = construct();
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    System.err.print(base[i][j].toString() + " ");
//                }
//                System.err.println();
//            }
            Frac[][] powd = pow(base, k);
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    System.err.print(powd[i][j].toString() + " ");
//                }
//                System.err.println();
//            }
            pw.println(powd[p0 - minP0][cnt0 - minP0].toVal());
        }
    }

    // template, actual code is in class Task.
    static long TIME_START, TIME_END;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));

        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.err.println("Memory increased: " + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.err.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    // Faster IO with BufferedReader wrapped with Scanner
//    static class Scanner {
//        StringTokenizer st;
//        BufferedReader br;
//
//        public Scanner(InputStream s) {
//            br = new BufferedReader(new InputStreamReader(s));
//        }
//
//        public Scanner(FileReader s) throws FileNotFoundException {
//            br = new BufferedReader(s);
//        }
//
//        public String next() throws IOException {
//            while (st == null || !st.hasMoreTokens())
//                st = new StringTokenizer(br.readLine());
//            return st.nextToken();
//        }
//
//        public int nextInt() throws IOException {
//            return Integer.parseInt(next());
//        }
//
//        public long nextLong() throws IOException {
//            return Long.parseLong(next());
//        }
//
//        public String nextLine() throws IOException {
//            return br.readLine();
//        }
//
//        public double nextDouble() throws IOException {
//            return Double.parseDouble(next());
//        }
//
//        public boolean ready() throws IOException {
//            return br.ready();
//        }
//    }
}