← 返回题目列表

Codeforces · 1151/F

F. 索尼娅和信息学

中文机器翻译题面 查看原题

一个名叫索尼娅的女孩正在克里姆兰王国的科学学院学习。计算机科学老师(索尼娅最喜欢的科目!)为她发明了一项任务。

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,仅包含数字 $$$0$$$ 和 $$$1$$$ 以及数字 $$$k$$$。正好 $$$k$$$ 次发生以下情况:

- 两个数字 $$$i$$$ 和 $$$j$$$ 被选择为等概率,使得 ($$$1 \leq i < j \leq n$$$)。
- $$$i$$$ 和 $$$j$$$ 位置中的数字被交换。

Sonya 的任务是求所有操作完成后 $$$a$$$ 数组按非降序排序的概率。她向你寻求帮助。帮助索尼娅解决这个问题。

可以证明,期望的概率要么是 $$$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}$$$ $$$\pmod {10^9+7}$$$,其中 $$$P$$$ 和 $$$Q$$$ 已在上面定义。

示例

输入 #1

3 2
0 1 0

输出 #1

333333336

输入 #2

5 1
1 1 1 0 0

输出 #2

0

输入 #3

6 4
1 0 0 1 1 0

输出 #3

968493834

注意

在第一个示例中,在应用两个操作后,最终数组 $$$a$$$ 的所有可能变体:$$$(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$$$。