CF1151F Sonya and Informatics

克雷姆兰王国的科学高中里有一个名叫 Sonya 的女孩。她最喜欢的学科是信息学，信息学老师为她出了一道题。 给定一个长度为 $n$ 的数组 $a$，数组元素仅包含 $0$ 和 $1$，以及一个整数 $k$。接下来恰好进行 $k$ 次如下操作： - 每次等概率地选择两个数 $i$ 和 $j$，满足 $1 \leq i < j \leq n$。 - 交换 $a$ 数组中第 $i$ 和第 $j$ 个位置的数。 Sonya 的任务是求出，所有操作完成后，数组 $a$ 恰好为非递减有序的概率。她向你寻求帮助。请你帮 Sonya 解决这个问题。 可以证明，所求概率要么为 $0$，要么可以表示为 $\dfrac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数，且 $Q \not\equiv 0~\pmod {10^9+7}$。

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 100, 1 \leq k \leq 10^9$），分别表示数组 $a$ 的长度和操作次数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 1$），表示数组 $a$ 的内容。

如果所求概率为 $0$，输出 $0$；否则输出 $P \cdot Q^{-1} \bmod {10^9+7}$，其中 $P$ 和 $Q$ 如上所述。

在第一个样例中，经过恰好两次操作后，所有可能的最终数组为：$(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)$。因此，答案为 $\dfrac{3}{9}=\dfrac{1}{3}$。 在第二个样例中，经过一次操作后，数组不会变为非递减有序，因此答案为 $0$。 由 ChatGPT 4.1 翻译