#P16920. [Ontak2025]随机排序

[Ontak2025]随机排序

题目描述

给定一个长度为 nn 的 01 序列 (a1,a2,…,an)(a_1,a_2,\ldots,a_n)。

一次操作中,从所有满足 1≤i<j≤n1\le i<j\le n 的位置对中等概率随机选出一对 (i,j)(i,j),然后交换 aia_i 与 aja_j。

恰好执行 kk 次操作后,求整个序列成为非降序序列的概率。

该概率一定可以写成最简分数 P/QP/Q。输出 P⋅Q−1 mod (109+7)P\cdot Q^{-1}\bmod(10^9+7)。

输入格式

第一行两个整数 n,kn,k:

  • 2≤n≤10002\le n\le1000;
  • 1≤k≤1091\le k\le10^9。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 ai∈{0,1}a_i\in\{0,1\}。

输出格式

输出一个整数,表示目标概率在模 109+710^9+7 意义下的值。

样例 1

3 2
0 1 0
333333336

样例 2

5 1
1 1 1 0 0
0

样例 3

6 4
1 0 0 1 1 0
968493834

子任务

子任务 额外限制 分值
1 n,k≤10n,k\le10 11
2 n≤100, k≤100000n\le100,\ k\le100000 23
3 n≤100n\le100 39
4 无额外限制 27