P11028 [COTS 2020] Totoro

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

You are given $K$ permutations $\pi_1,\pi_2,\cdots,\pi_K$ of $1 \sim N$。 Find the expected number of inversions of a permutation in the permutation group $G(S,\circ)$, where the binary operation $\circ$ is **permutation composition**, and for all $1 \le i \le K$, we have $\pi_i \in S$。 More specifically, we define $(\pi \circ \tau)(i) = \pi(\tau(i))$。 The group $G(S,\circ)$ is an algebraic structure satisfying the following properties: - Closure: for all $a,b \in S$, we have $a \circ b \in S$； - Associativity: for all $a,b,c \in S$, we have $(a \circ b) \circ c = a \circ (b \circ c)$； - Identity element: there exists $e \in S$ such that for all $a \in S$, $a \circ e = e \circ a = a$； - Inverse element: for all $a \in S$, there exists $b \in S$ such that $a \circ b = b \circ a = e$。 Define $\mathcal{L}(\pi)$ as the number of inversions of $\pi$, i.e. $\displaystyle \mathcal{L}(\pi)=\sum_{1\le i\lt j\le n}[\pi(i)\gt \pi(j)]$。Compute $\displaystyle \frac{1}{|S|}\sum_{\pi \in S} \mathcal{L}(\pi)$。 Output the answer modulo $(10^9+7)$。

The first line contains two positive integers $K, N$。 The next $K$ lines each contain $N$ positive integers describing $\pi_i$。

Output one integer: the answer modulo $(10^9+7)$。

#### Sample Explanation - Sample $1$: $S=\{[2,3,1],[3,1,2],[1,2,3]\}$。The expected number of inversions is $\frac{1+2+0}{3}=\frac{4}{3}$。 - Sample $2$: It can be proven that $|S| = 5!$, meaning that $S$ contains all permutations of $1 \sim 5$。 - Sample $3$: Here $|S|=20$。The true value of the answer is $\frac{149}{10}$。 #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $1 \le K \le 10$； - $1 \le N \le 2\, 500$； - $\pi_i$ is a permutation of $1 \sim N$。 | Subtask ID | $N\le $ | $K\le $ | Special Property | Score | | :--: | :--: | :--: | :--: | :--: | | $ 1 $ | $9$ | $ 10 $ | None | $ 7 $ | | $ 2 $ | $2\,500$ | $1$ | Yes | $ 8 $ | | $ 3 $ | $2\, 500$ | $1$ | None | $ 25 $ | | $ 4 $ | $2\, 500$ | $10$ | None | $ 60 $ | Special Property: for all $1 \le i \le K$, there exists a permutation $a$ of $1 \sim N$ such that $\pi_i(a_1)=a_2,\pi_{i}(a_2)=a_3,\cdots,\pi_i(a_n)=a_1$。 Translated by ChatGPT 5