题目描述

给定一个长度为 $n$ 的 01 序列 $(a_1,a_2,\ldots,a_n)$。

一次操作中，从所有满足 $1\le i<j\le n$ 的位置对中等概率随机选出一对 $(i,j)$，然后交换 $a_i$ 与 $a_j$。

恰好执行 $k$ 次操作后，求整个序列成为非降序序列的概率。

该概率一定可以写成最简分数 $P/Q$。输出 $P\cdot Q^{-1}\bmod(10^9+7)$。

输入格式

第一行两个整数 $n,k$：

• $2\le n\le1000$；
• $1\le k\le10^9$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i\in\{0,1\}$。

输出格式

输出一个整数，表示目标概率在模 $10^9+7$ 意义下的值。

样例 1

3 2
0 1 0

333333336

样例 2

5 1
1 1 1 0 0

0

样例 3

6 4
1 0 0 1 1 0

968493834

子任务