P10353 [PA 2024] Grupa permutacji

PA 2024 2A

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 2 [Grupa permutacji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/gru/)** 在本题中，我们将处理 $n$ 个元素的排列。$n$ 个元素的排列是由 $1$ 到 $n$（包含两端）的 $n$ 个不同的自然数组成的序列。将排列 $a_1,a_2,\ldots,a_n$ 和排列 $b_1,b_2,\ldots,b_n$ 复合起来，会得到排列 $a_{b_1},a_{b_2},\ldots,a_{b_n}$。我们称任意满足 $ip_j$ 的数对 $(i,j)$ 为排列 $p_1,p_2,\ldots,p_n$ 的逆序对。 Bytie 是 $n$ 个元素的排列的忠实粉丝。他非常喜欢它们，并且其中有一些是他最喜欢的。他决定开始在一张纸上写下通过复合他最喜欢的排列（以任何顺序，也许多次使用其中一些排列）能得到的所有排列，并小心翼翼地保证不写出任何排列超过一次。 毫无疑问，他很快就用完了纸张。然后 Bytie 有一个问题：如果他列出所有可能的排列，它们平均会有多少个逆序对？ 帮他写一个程序来计算这个值。更具体地说，输出答案对 $10^9+7$ 取模后的值（详见「输出格式」部分）。

第一行包含两个整数 $n$ 和 $k\ (1\le n,k\le 3\,000)$，分别表示排列的长度和 Bytie 最喜欢的排列个数。 接下来 $k$ 行，第 $i$ 行包含 $n$ 个互不相同的整数 $a_{i,1},a_{i,2},\ldots,a_{i,n}\ (1\le a_{i,j}\le n)$，表示 Bytie 第 $i$ 个最喜欢的排列。

输出一行一个整数，表示 Bytie 可能写下的所有排列中逆序对数的平均值模 $10^9+7$ 后的结果。 形式化地说，令结果为 $\frac{p}{q}$，其中 $q\neq 0$ 且 $\gcd(p,q)=1$。则输出 $p\cdot q^{-1}\pmod{10^9+7}$，其中 $q^{-1}$ 表示在 $1,2,\ldots,10^9+6$ 中唯一满足 $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$ 的整数。 可以证明，对于所有满足条件的测试数据，其结果是一个有理数，其不可约形式的分母不能被 $10^9+7$ 整除。

在第一组样例中，Bytie 会写下排列 $\{1,2,3\}$（有 $0$ 个逆序对），排列 $\{2,3,1\}$（有 $2$ 个逆序对）和排列 $\{3,1,2\}$（有 $2$ 个逆序对）。因此平均逆序对个数为 $\frac{4}{3}$。且 $3^{-1}\equiv 333333336\pmod{10^9+7}$，因此答案为 $333333336\cdot 4\equiv 1333333344\equiv 333333337\pmod{10^9+7}$。 在第二组样例中，Bytie 会写下 $5$ 个元素的所有排列。容易证明它们平均有 $5$ 个逆序对。