问题描述

小核桃有一道数学题，他并不会做。为了解决这个问题，现在他决定用这道题来考你。

具体是这样的，小核桃将会给你一个长度为 $n$，且只包含 $0$ 和 $1$ 的数组 $a$。然后这个数组 $a$ 将会经历 $k$ 次下述变化：

1. 等概率选择两个整数 $i，j（1 \leq i \lt j \leq n）$
2. 将 $a_i$ 和 $a_j$ 交换位置。

你需要告诉小核桃，经过 $k$ 次这种变换后，数组 $a$ 恰好变为非降序的概率。

可以证明的是，最终概率要么是 $0$, 要么可以被表达为 $\frac{P}{Q}$，$P$ 与 $Q$ 互质，且 $Q \not\equiv 0 (mod \; 1e9+7)$

输入描述

第一行包含两个正整数 $n$ 和 $k$，分别表示数组 $a$ 的长度和变化的次数。

第二行包含 $n$ 个整数 $a_1, a_2,...,a_n(0\leq a_i \leq 1)$

输出描述

如果概率为 $0$，那么就直接输出 $0$，否则输出 $PQ^{-1} (mod \; 1e9+7)$

3 2
0 1 0

333333336

5 1
1 1 1 0 0

0

样例解释

对于第一个样例，在经过两次操作后，所有可能的数组的最终形态为:

$(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)$

所以，答案为 $\frac{3}{9} = \frac{1}{3}$

对于样例二，经过一次操作后，数组绝无可能变为非降序的数组，因此概率为 $0$

数据范围与约定

大样例

大样例下载