题目背景

译自 Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) 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 3
2 3 1

333333337

2 5
4 2 1 3 5
2 5 4 3 1

5

1 9
3 4 5 6 7 8 1 9 2

300000017

提示

样例解释

• 样例 $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$ 的排列。

特殊性质：$\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$。