В этой задаче мы будем работать с перестановками длины $n$. Каждая такая перестановка представляет собой последовательность из $n$ различных натуральных чисел от $1$ до $n$ включительно. Композицией перестановки $a_1, a_2, \dots, a_n$ с перестановкой $b_1, b_2, \dots, b_n$ называется перестановка $a_{b_1}, a_{b_2}, \dots, a_{b_n}$. Инверсией в перестановке $p_1, p_2, \dots, p_n$ называется любая пара индексов $(i, j)$ такая, что $i < j$ и $p_i > p_j$.
Байтек — большой поклонник перестановок длины $n$. Он любит их настолько, что даже выделил среди них $k$ своих любимых. Он решил выписать на лист бумаги все перестановки, которые можно получить, составляя композиции из его любимых перестановок (в любом порядке и, возможно, используя некоторые из них многократно), при этом он тщательно следил за тем, чтобы не выписать ни одну перестановку более одного раза.
Неудивительно, что у него довольно быстро закончилась бумага. Тогда Байтек задался вопросом: если бы он выписал все достижимые перестановки, то сколько в среднем они имели бы инверсий?
Помогите ему и напишите программу, которая вычислит это значение. Точнее, ваша задача — вывести искомое значение по модулю $10^9 + 7$ (подробнее об этом в разделе Выходные данные).
Входные данные
В первой строке входных данных находятся два целых числа $n$ и $k$ ($1 \le n, k \le 3000$), обозначающие соответственно длину перестановки и количество любимых перестановок Байтека.
В следующих $k$ строках находятся сами перестановки. В $i$-й из этих строк содержится последовательность из $n$ различных целых чисел $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$), соответствующая $i$-й любимой перестановке Байтека.
Выходные данные
В единственной строке вывода должно содержаться одно целое число, равное среднему количеству инверсий среди всех перестановок, которые мог бы выписать Байтек, по модулю $1\,000\,000\,007$.
Формально, пусть результат равен $\frac{p}{q}$, где $q \neq 0$ и $\text{НОД}(p, q) = 1$. Тогда необходимо вывести одно число $p \cdot q^{-1} \pmod{1\,000\,000\,007}$, где $q^{-1}$ — единственное число из множества $1, 2, \dots, 1\,000\,000\,006$ такое, что $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$.
Можно доказать, что для всех тестов, удовлетворяющих условиям задачи, результат является рациональным числом, знаменатель которого в несократимом виде не делится на $1\,000\,000\,007$.
Примеры
Пример 1
3 1 2 3 1
333333337
Пример 2
5 2 2 1 3 4 5 2 3 4 5 1
5
Примечание
В первом примере Байтек выписал бы перестановку $\{1, 2, 3\}$, имеющую ноль инверсий, $\{2, 3, 1\}$, имеющую две инверсии, и $\{3, 1, 2\}$, также имеющую две инверсии. Среднее количество инверсий составляет $\frac{4}{3}$. Так как $3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$, получаем $333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$.
Во втором примере Байтек выписал бы все перестановки из 5 элементов. Легко показать, что в среднем они имеют ровно 5 инверсий.