CF1043D Mysterious Crime

Acingel 是一个小镇。这里只有一位医生——Ada 小姐。她非常友好，从来没有人说过她的坏话，所以谁能想到 Ada 会被发现死在自己家中呢？世界著名侦探 Gawry 先生被指派来查明凶手。他询问了 Ada 的 $m$ 位邻居，了解在那不幸的一天有哪些客户拜访过她。我们将客户编号为 $1$ 到 $n$。每位邻居的证词是这些编号的一个排列，描述了该邻居看到客户的顺序。 然而，有些事实非常可疑——为什么在某些排列中，某个客户早上被看到，而在其他排列中却是晚上？“早上有些邻居一定在睡觉！”——Gawry 想道——“晚上又太黑，看不清楚是谁……”。现在他想在每个排列中删除一些前缀和一些后缀（前缀和后缀都可以为空），使得删除后剩下的部分非空且彼此相等——这样一些潜在的嫌疑人可能会被排除，但证词之间就不会互相矛盾了。 他想知道有多少种方法可以做到这一点？如果剩下的公共部分不同，则认为是不同的方法。

第一行包含两个整数 $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$ 每个数字恰好出现一次）。

输出一个整数，表示有多少种方法可以在每个排列中删除一些前缀和一些后缀（可以为空），使得剩下的部分非空且彼此相等。

在第一个样例中，所有可能的公共部分为 $[1]$、$[2]$、$[3]$ 和 $[2, 3]$。 在第二个和第三个样例中，只能留下长度为 $1$ 的公共部分。 由 ChatGPT 4.1 翻译