CF1151F.Sonya and Informatics

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 \leq i \lt j \leq 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 $\dfrac{P}{Q}$, where $P$ and $Q$ are coprime integers and $Q \not\equiv 0~\pmod {10^9+7}$.

一位名叫索尼娅的女孩正在克雷姆兰德王国的科学中学学习。她的计算机科学老师（这门课是索尼娅最喜爱的科目！）为她设计了一道题目。

给定一个长度为 $n$ 的数组 $a$，其中仅包含数字 $0$ 和 $1$，以及一个整数 $k$。接下来恰好执行 $k$ 次如下操作：

• 等概率地随机选取两个下标 $i$ 和 $j$，满足 $1 \leq i \lt j \leq n$；
• 交换数组中第 $i$ 个位置与第 $j$ 个位置上的数。

索尼娅的任务是：求经过全部 $k$ 次操作后，数组 $a$ 恰好按非递减顺序排列的概率。她向你寻求帮助，请你协助索尼娅解决这个问题。

可以证明：所求概率要么为 $0$，要么可表示为 $\dfrac{P}{Q}$ 的形式，其中 $P$ 与 $Q$ 互质，且 $Q \not\equiv 0~\pmod {10^9+7}$。

The first line contains two integers $n$ and $k$ ($2 \leq n \leq 100, 1 \leq k \leq 10^9$) — the length of the array $a$ and the number of operations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 1$) — the description of the array $a$.

第一行包含两个整数 $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$。

If the desired probability is $0$, print $0$, otherwise print the value $P \cdot Q^{-1}$ $\pmod {10^9+7}$, where $P$ and $Q$ are defined above.

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

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 $\dfrac{3}{9}=\dfrac{1}{3}$.

In the second example, the array will not be sorted in non-decreasing order after one operation, therefore the answer is $0$.

在第一个例子中，恰好执行两次操作后，最终数组 $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$。