Acingel 是一个小镇。这里只有一位医生——艾达小姐。她很友善,从来没有人说过她的坏话,所以谁能想到艾达会被发现死在她的家里呢?世界著名侦探高里先生受命寻找罪犯。他向艾达的$$$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$$$ 的每个数字恰好出现一次)。
输出
输出一个整数,表示删除每个排列的某些前缀和某些后缀的方法数(可能为空),使得剩余部分相等且非空。
示例
输入 #1
3 2 1 2 3 2 3 1
输出 #1
4
输入 #2
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
输出 #2
5
输入 #3
2 2 1 2 2 1
输出 #3
2
注意
在第一个示例中,所有可能的公共部分是 $$$[1]$$$、$$$[2]$$$、$$$[3]$$$ 和 $$$[2, 3]$$$。
在第二个和第三个示例中,只能保留长度为 $$$1$$$ 的公共部分。