“Tonari no To to ro Totoro, To to ro Totoro”

Totoro has $K$ permutations $p_1, \dots, p_K$ of length $N$.

Let $S$ be the set of all permutations that can be obtained by composing a finite number of permutations $p_i$. The composition of two permutations $\pi$ and $\tau$ at position $i$ has the element $\pi(\tau(i))$. For example, the composition of permutations $\pi = (1, 3, 2)$ and $\tau = (2, 3, 1)$ is equal to $\pi \circ \tau = (3, 2, 1)$. It is allowed to compose the same permutations multiple times.

It is clear that $S$ is a finite set, as it is contained in the set of all permutations of length $N$.

We are interested in the average number of inversions of permutations in the set $S$. The number of inversions $\mathcal{I}(\pi)$ of a permutation $\pi$ is equal to the number of ordered pairs of numbers $1 \le i < j \le N$ for which $\pi(i) > \pi(j)$.

Formally, we are interested in $\frac{1}{|S|} \sum_{\pi \in S} \mathcal{I}(\pi)$. It can be proven that the answer can be written as an irreducible fraction $\frac{A}{B}$, where $B$ is not divisible by $10^9 + 7$. Output $A \cdot B^{-1}$ modulo $10^9 + 7$, i.e., the number $X$ such that $0 \le X < 10^9 + 7$ and $X \cdot B \equiv A \pmod{10^9 + 7}$.

Input

The first line contains natural numbers $K$ and $N$ from the problem description.

In the $i$-th of the following $K$ lines, there is a permutation $p_i$, represented as a sequence of $N$ distinct numbers from $1$ to $N$, separated by spaces.

Output

In a single line, output the answer modulo $10^9 + 7$.

Subtasks

Note: A permutation is a cycle if the numbers $1, 2, \dots, n$ can be ordered into a sequence $a_1, a_2, \dots, a_n$ such that $p(a_1) = a_2, p(a_2) = a_3, \dots, p(a_n) = a_1$.

Examples

Input 1

1 3
2 3 1

Output 1

333333337

Note 1

Note that $S = \{(2, 3, 1), (3, 1, 2), (1, 2, 3)\}$. The first permutation has two inversions, the second also has two inversions, and the last one is the identity and has no inversions. Therefore, the average number of inversions is $\frac{4}{3}$, which corresponds to the printed number modulo $10^9 + 7$.

Input 2

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

Output 2

5

Note 2

It can be verified that $S$ is equal to the set of all permutations of the set $\{1, 2, 3, 4, 5\}$, i.e., by composing the given permutations, it is possible to obtain all other permutations.

Input 3

1 9
3 4 5 6 7 8 1 9 2

Output 3

300000017

Note 3

In this example, $|S| = 20$, and the answer is equal to the fraction $\frac{149}{10}$ modulo $10^9 + 7$.