Background

PA 2024 2A

Problem Description

This problem is translated from PA 2024 Round 2 Grupa permutacji.

In this problem, we deal with permutations of $n$ elements. A permutation of $n$ elements is a sequence of $n$ distinct natural numbers from $1$ to $n$ (inclusive). Composing the permutation $a_1,a_2,\ldots,a_n$ with the permutation $b_1,b_2,\ldots,b_n$ results in the 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 of the permutation $p_1,p_2,\ldots,p_n$.

Bytie is a loyal fan of permutations of $n$ elements. He likes them very much, and some of them are his favorites. He decided to start writing on a piece of paper all permutations that can be obtained by composing his favorite permutations (in any order, possibly using some of them multiple times), carefully making sure that he does not write any permutation more than once.

Without a doubt, he quickly ran out of paper. Then Bytie has a question: if he listed all possible permutations, how many inversions would they have on average?

Help him write a program to compute this value. More specifically, output the answer 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.

The next $k$ lines each contain $n$ pairwise distinct integers $a_{i,1},a_{i,2},\ldots,a_{i,n}\ (1\le a_{i,j}\le n)$, describing Bytie’s $i$-th favorite permutation.

Output Format

Output one integer in a single line: the average number of inversions among all permutations that Bytie may write down, taken modulo $10^9+7$.

Formally, let the result be $\frac{p}{q}$, where $q\neq 0$ and $\gcd(p,q)=1$. 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 testdata, the result is a rational number whose denominator in lowest terms is not divisible by $10^9+7$.

3 1
2 3 1

333333337

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

5

Hint

In the first sample, Bytie will write the permutation $\{1,2,3\}$ (which has $0$ inversions), the permutation $\{2,3,1\}$ (which has $2$ inversions), and the permutation $\{3,1,2\}$ (which has $2$ inversions). Therefore, the average number of inversions is $\frac{4}{3}$. Also, $3^{-1}\equiv 333333336\pmod{10^9+7}$, so the answer is $333333336\cdot 4\equiv 1333333344\equiv 333333337\pmod{10^9+7}$.

In the second sample, Bytie will write all permutations of $5$ elements. It is easy to prove that their average number of inversions is $5$.

Translated by ChatGPT 5