E. Войтек и карточные фокусы
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Войтек только что выиграл олимпиаду по математике в Байтландии! Приз восхитителен - отличная книга под названием 'Карточные фокусы для чайников.' 'Отлично!' он подумал, 'Наконец-то я смогу воспользоваться запылившейся колодой карт, которая без дела лежит у меня на столе!'

Первая глава книги это 'Как перемешать $$$k$$$ карт в любом порядке, который вы хотите.' Формально это список из $$$n$$$ детерминированных методов перемешать $$$k$$$ карт. Более формально, $$$i$$$-й метод может быть описан перестановкой $$$(P_{i,1}, P_{i,2}, \dots, P_{i,k})$$$ целых чисел от $$$1$$$ до $$$k$$$. Если мы упорядочим карты в колоде от $$$1$$$ до $$$k$$$ сверху вниз, тогда $$$P_{i,j}$$$ обозначает номер $$$j$$$-й карты сверху колоды после перемешивания.

Войтек хочет научиться только некоторым фокусам сегодня. Он выберет два целых числа $$$l, r$$$ ($$$1 \le l \le r \le n$$$), и запомнит все фокусы от $$$l$$$-го до $$$r$$$-го, включительно. Затем он возьмет отсортированную колоду из $$$k$$$ карт и будет применять случайные запомненные фокусы, пока ему не станет скучно. Он все еще любит математику, и поэтому заинтересовался: а сколько различных колод он может получить?

Войтек все еще не выбрал $$$l$$$ и $$$r$$$, но ему очень любопытно. Так он определил $$$f(l, r)$$$ как количество различных колод которое он может получить, если выучит все фокусы от $$$l$$$-го до $$$r$$$-го, включительно. Чему равно

$$$$$$\sum_{l=1}^n \sum_{r=l}^n f(l, r)?$$$$$$

Входные данные

В первой строке записано два целых числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le k \le 5$$$) — количество фокус и карт в колоде Войтека.

Каждая из следующих $$$n$$$ строк описывает один фокус и содержит $$$k$$$ различных целых чисел $$$P_{i,1}, P_{i,2}, \dots, P_{i, k}$$$ ($$$1 \le P_{i, j} \le k$$$).

Выходные данные

Выведите сумму, описанную в условии.

Примеры
Входные данные
3 3
2 1 3
3 1 2
1 3 2
Выходные данные
25
Входные данные
2 4
4 1 3 2
4 3 1 2
Выходные данные
31
Примечание

Рассмотрим первый пример:

  • Первый фокус меняет две верхние карты.
  • Второй фокус берет карту снизу колоды и кладет ее наверх.
  • Третий фокус меняет две нижние карты.

Первый и третий фокусы сами по себе позволяют получить только две колоды (либо две карты поменяны местами, либо нет). Таким образом, $$$f(1, 1) = f(3, 3) = 2$$$.

Второй фокус позволяет совершать циклические сдвиги, таким образом $$$f(2,2)=3$$$.

Оказывается, что два первых и два последних фокуса позволяют получить все возможные перестановки колоды Войтека. Таким образом $$$f(1,2) = f(2,3) = f(1,3) = 3! = 6$$$.