Expected Inversion Count in a Permutation Group

Given K permutations \(\pi_1, \pi_2, \ldots, \pi_K\) of the set \(\{1,2,\ldots, N\}\), these permutations are all contained in a set \(S\) such that \(S\) forms a group under the binary operation of composition \(\circ\). For any two permutations \(\pi\) and \(\tau\) in \(S\), their composition is defined by \((\pi\circ \tau)(i)=\pi(\tau(i))\) for all \(1\le i\le N\).

The group \(G(S, \circ)\) satisfies the following properties:

• Closure: For all \(a,b\in S\), \(a\circ b\in S\).
• Associativity: For all \(a,b,c\in S\), \((a\circ b)\circ c = a\circ (b\circ c)\).
• Identity element: There exists \(e\in S\) such that for every \(a\in S\), \(a\circ e = e\circ a = a\).
• Inverse element: For every \(a\in S\), there exists \(b\in S\) such that \(a\circ b = b\circ a = e\).

Define the inversion count \(\mathcal{L}(\pi)\) of a permutation \(\pi\) as:

[ \mathcal{L}(\pi)=\sum_{1\le i<j\le N}[\pi(i)>\pi(j)], ]

Compute the expected number of inversions among all permutations in the group \(G(S, \circ)\):

[ E = \frac{1}{|S|}\sum_{\pi \in S} \mathcal{L}(\pi) \mod (10^9+7). ]

Note that the answer should be output modulo \(10^9+7\).

inputFormat

The first line contains two integers \(N\) and \(K\), where \(N\) is the size of the permutation and \(K\) is the number of given generators.

Each of the next \(K\) lines contains \(N\) space-separated integers representing a permutation of \(\{1,2,\ldots,N\}\>.

outputFormat

Output a single integer, the expected inversion count over all elements of the group \(G(S, \circ)\), computed modulo \(10^9+7\). Since the expected value is a rational number \(\frac{A}{B}\), output \(A\cdot B^{-1}\mod (10^9+7)\) where \(B^{-1}\) is the modular multiplicative inverse of \(B\) modulo \(10^9+7\).

sample

3 1
1 2 3

0