D. Загадочное преступление
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ацингел — достаточно маленький городок. В этом городке был всего один доктор — Мисс Ада. Она была очень дружелюбной и никто никогда не говорил про неё ничего плохого. Так что кто мог подумать, что Аду найдут мёртвой в собственном доме? Мистер Гаври, известный во всём мире детектив, был назначен найти преступника. Он опросил $$$m$$$ соседей Ады о клиентах, которые посетили её в тот злосчастный день. Давайте пронумеруем этих клиентов от $$$1$$$ до $$$n$$$. Свидетельством каждого соседа является перестановка этих чисел, которая описывает порядок, в котором этот сосед видел клиентов приходящими к Аде.

Однако некоторые факты выглядят достаточно подозрительно — как могло быть, что, согласно некоторым перестановкам некоторые клиенты были замечены утром, а согласно другим — вечером? «Утром некоторые из соседей скорее всего спали! — подумал Гаври, — А вечером слишком темно, чтобы видеть лица людей...». Теперь он хочет удалить из каждой перестановки некоторый префикс и некоторый суффикс (возможно, пустые) так, что оставшиеся части будут не пусты и равны друг другу. Возможно, часть потенциальных преступников пропадёт, но хотя бы не будет противоречий в свидетельствах соседей.

Сколькими способами он может это сделать? Два способа называются разными, если в них отличается оставшаяся общая часть.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le 10$$$) — количество подозреваемых и количество опрошенных соседей.

Каждая из следующих $$$m$$$ строк содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Гарантируется, что эти числа образуют перестановку (то есть каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз).

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

Выведите одно целое число — количество способов удалить из каждой перестановки некоторый префикс и суффикс (возможно, пустые) так, что оставшаяся часть была бы равной и непустой.

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

В первом примере общей частью может быть $$$[1]$$$, $$$[2]$$$, $$$[3]$$$ и $$$[2, 3]$$$.

Во втором и третьем примерах можно оставлять только общие части из $$$1$$$ элемента.