Sonya and Informatics
Contest: Codeforces Round 553 (Div. 2)
Difficulty rating: 2300
Tags: combinatorics, dp, matrices, probabilities

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 < 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}$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 2
0 1 0

Example output:
333333336

Example input:
5 1
1 1 1 0 0

Example output:
0

Editorial:
How to solve this problem in $$$\mathcal{O}(n\cdot k)$$$?
Let's find the answer using dynamic programming. Denote $$$cur$$$ as the number of zeroes in array $$$a$$$, and $$$dp_{i,j}$$$ as the number of rearrangements of array $$$a$$$ after $$$i$$$ operations and $$$j$$$ is equal to the number of zeroes on prefix of length $$$cur$$$. Denote $$$x$$$ as the number of zeroes on prefix of length $$$cur$$$. The initial state will be $$$dp_{0,x}=1$$$. Notice that the answer will be $$$\dfrac{dp_{k, cur}}{\sum_{i=0}^{cur}dp_{k, i}}$$$.
The transitions are not so hard. You must know the following values: the number of ones on prefix of length $$$cur$$$, the number of zeroes on prefix of length $$$cur$$$, the number of ones NOT on prefix of length $$$cur$$$ and the number of zeroes NOT on prefix of length $$$cur$$$. For example, you can find the number of pairs such that after we swap them the number of zeroes on prefix of length $$$cur$$$ is increased by one: the number of ones on prefix of length $$$cur$$$ multiply by the number of zeroes NOT on prefix of length $$$cur$$$. Also there are transitions when the number of zeroes on prefix of length $$$cur$$$ remains the same, and when it decreased by one (you can find them by yourself).
To solve the original problem we must create the transition matrix and find the answer using matrix multiplication with binary exponentiation.
Also you must know how to find the modular multiplicative inverse to find the answer.
Complexity is $$$\mathcal{O}(n^3\cdot \log{k})$$$.