Problem Background

PA 2024 2A

Problem Description

This problem is translated from PA 2024 Round 2 Permutation Group

In this problem, we will deal with permutations of $n$ elements. A permutation of $n$ elements is a sequence consisting of $n$ distinct natural numbers from $1$ to $n$ inclusive. Composing permutation $a_1,a_2,\ldots,a_n$ with permutation $b_1,b_2,\ldots,b_n$ results in permutation $a_{b_1},a_{b_2},\ldots,a_{b_n}$. We call any pair $(i,j)$ such that $i<j$ and $p_i>p_j$ an inversion pair of the permutation $p_1,p_2,\ldots,p_n$.

Bytie is a devoted fan of permutations of $n$ elements. He loves them very much, and some of them are his favorites. He decided to start writing down all permutations that can be obtained by composing his favorite permutations (in any order, possibly using some of them multiple times) on a piece of paper, carefully ensuring that no permutation is written more than once.

Undoubtedly, he quickly ran out of paper. Then Bytie had a question: if he listed all possible permutations, on average, how many inversion pairs would they have?

Help him write a program to calculate this value. More specifically, output the result modulo $10^9+7$ (see the "Output Format" section for details).

Input Format

The first line contains two integers $n$ and $k\ (1\le n,k\le 3\,000)$, representing the length of the permutations and the number of Bytie's favorite permutations, respectively.

The next $k$ lines, the $i$-th line contains $n$ distinct integers $a_{i,1},a_{i,2},\ldots,a_{i,n}\ (1\le a_{i,j}\le n)$, representing Bytie's $i$-th favorite permutation.

Output Format

Output a single integer, representing the average number of inversion pairs in all permutations that Bytie could write down, modulo $10^9+7$.

Formally, let the result be $\frac{p}{q}$, where $q\neq 0$ and $\gcd(p,q)=1$. Then output $p\cdot q^{-1}\pmod{10^9+7}$, where $q^{-1}$ is the unique integer in $1,2,\ldots,10^9+6$ such that $q\cdot q^{-1}\equiv 1\pmod{10^9+7}$.

It can be proven that for all valid test cases, the result is a rational number whose irreducible form has a denominator not divisible by $10^9+7$.

Sample Input and Output

Sample Input #1

3 1
2 3 1

Sample Output #1

333333337

Sample Input #2

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

Sample Output #2

5

Notes

In the first sample, Bytie will write down the permutations $\{1,2,3\}$ (with $0$ inversion pairs), $\{2,3,1\}$ (with $2$ inversion pairs), and $\{3,1,2\}$ (with $2$ inversion pairs). Therefore, the average number of inversion pairs is $\frac{4}{3}$. Since $3^{-1}\equiv 333333336\pmod{10^9+7}$, the answer is $333333336\cdot 4\equiv 1333333344\equiv 333333337\pmod{10^9+7}$.

In the second sample, Bytie will write down all permutations of $5$ elements. It is easy to prove that they average $5$ inversion pairs.

见题面 Input 部分

见题面 Output 部分