P11028 [COTS 2020] 龙猫 Totoro

译自 [Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2020/) D2T3。$\texttt{1s,0.5G}$。

给定 $K$ 个 $1\sim N$ 的排列 $\pi_1,\pi_2,\cdots,\pi_K$。 求出排列群 $G(S,\circ)$ 中的排列的逆序对期望值。其中二元运算 $\circ$ 为**置换**，$\forall 1\le i\le K$，都有 $\pi_i\in S$。 具体地说，我们定义 $(\pi\circ \tau)(i)=\pi(\tau(i))$。 群 $G(S,\circ)$ 是满足如下性质的代数结构： - 封闭性：$\forall a,b\in S$，都有 $a\circ b\in S$； - 结合律：$\forall a,b,c\in S$，都有 $(a\circ b)\circ c=a\circ (b\circ c)$； - 幺元：存在 $e\in S$，对于 $\forall a\in S$，都有 $a\circ e=e\circ a=a$； - 逆元：$\forall a\in S$，存在 $b\in S$，使得 $a\circ b=b\circ a=e$。 定义 $\mathcal{L}(\pi)$ 为 $\pi$ 的逆序对数，即 $\displaystyle \mathcal{L}(\pi)=\sum_{1\le i\lt j\le n}[\pi(i)\gt \pi(j)]$，求出 $\displaystyle \frac{1}{|S|}\sum_{\pi \in S} \mathcal{L}(\pi)$。 答案对 $(10^9+7)$ 取模。

第一行，两个正整数 $K,N$。 接下来 $K$ 行，第 $i$ 行 $N$ 个正整数描述 $\pi_i$。

输出一行一个整数，即答案对 $(10^9+7)$ 取模后的结果。

#### 样例解释 - 样例 $1$ 解释：$S=\{[2,3,1],[3,1,2],[1,2,3]\}$。逆序对期望值为 $\frac{1+2+0}{3}=\frac{4}{3}$。 - 样例 $2$ 解释：可以证明 $|S|=5!$，即 $S$ 中包含了 $1\sim 5$ 的所有排列。 - 样例 $3$ 解释：此时 $|S|=20$，答案真实值为 $\frac{149}{10}$。 #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le K\le 10$； - $1\le N\le 2\, 500$； - $\pi_i$ 是 $1\sim N$ 的排列。 | 子任务编号 | $N\le $ | $K\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | :--: | | $ 1 $ | $9$ | $ 10 $ | 无 | $ 7 $ | | $ 2 $ | $2\,500$ | $1$ | 有 | $ 8 $ | | $ 3 $ | $2\, 500$ | $1$ | 无 | $ 25 $ | | $ 4 $ | $2\, 500$ | $10$ | 无 | $ 60 $ | 特殊性质：$\forall 1\le i\le K$，存在 $1\sim N$ 的排列 $a$，使得 $\pi_i(a_1)=a_2,\pi_{i}(a_2)=a_3,\cdots,\pi_i(a_n)=a_1$。