Background

Translated from Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection) D2T3。$\texttt{1s,0.5G}$。

Problem Description

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)$。

Input Format

The first line contains two positive integers $K, N$。

The next $K$ lines each contain $N$ positive integers describing $\pi_i$。

Output Format

Output one integer: the answer modulo $(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

Hint

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$。

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