题目描述

最近小 Z 学会了字符串哈希算法。通俗地讲，就是把一个字符串映射到一个整数的方法。

一种通用的哈希方法如下：对于一个长度为 $n$ 字符串 $s$ (下标从 $1$ 开始) :

$$\begin{aligned} \operatorname{hash}(s) & =\bigg(s[1]+s[2] \cdot p+s[3] \cdot p^2+\ldots+s[n] \cdot p^{n-1}\bigg) \bmod m =\bigg(\sum_{i=0}^{n-1} s[i+1] \cdot p^i\bigg) \bmod m \end{aligned}$$

其中 $p,m$ 是某个提前选定的正整数。这种哈希方法我们称为多项式哈希。

但小 Z 并不理解如何选择合适的 $p$ 和 $m$ ，所以他经常遇到哈希冲突的情况。考虑字符串 $s$ 的两个子串 $s_1,s_2$，如果 $s_1\not = s_2$ 但 $hash(s_1)=hash(s_2)$ ，我们就说 $s_1,s_2$之间发生了哈希冲突。

现在给定一个长度为 $n$ 的字符串 $s$，和两个小 Z 选定好的正整数 $p,m$。他想请你帮他计算有多少个四元组 $(l_1,r_1,l_2,r_2)$，满足 $1\le l_1\le r_1\le n, 1\le l_2\le r_2\le n$，并且 $s[l_1,r_1]$ 和 $s[l_2,r_2]$ 之间发生了哈希冲突。这里 $s[l,r]$ 表示 $s$ 中第 $l$ 个字符到第 $r$ 个字符构成的子串。

输入格式

从 collision.in 文件读入数据。

第一行包含三个整数 $n, p, m$.

第二行包含 $n$ 个正整数 $s[1],s[2],\dots,s[n]$，第 $i$ 个正整数代表字符串第 $i$ 个字符对应的值。

输出格式

输出到 collision.out 文件。

输出一个整数，代表答案。

样例

4 2 6
1 2 1 2

4

样例中每个子串的哈希值如下：

$hash(s[1,1])=1$

$hash(s[2,2])=2$

$hash(s[3,3])=1$

$hash(s[4,4])=2$

$hash(s[1,2])=(1 + 2 \cdot 2)\bmod 6 = 5$

$hash(s[2,3])=(2 + 1\cdot 2)\bmod 6 = 4$

$hash(s[3,4])=(1 + 2\cdot 2)\bmod 6 = 5$

$hash(s[1,3])=(1+2\cdot 2 + 1\cdot 2^2)\bmod 6 = 3$

$hash(s[2,4])=(2+1\cdot 2 + 2\cdot 2^2)\bmod 6 = 0$

$hash(s[1,4])=(1 + 2\cdot 2 + 1\cdot 2^2 + 2\cdot 2^3)\bmod 6 = 1$

答案中发生哈希冲突的所有四元组：

• $l_1=1,r_1=1,l_2=1,r_2=4$

• $l_1=3,r_1=3,l_2=1,r_2=4$

• $l_1=1,r_1=4,l_2=1,r_2=1$

• $l_1=1,r_1=4,l_2=3,r_2=3$

样例 2

点击链接 ex_collision2.in 和 ex_collision2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据，$1\le n\le 3000, 1\le p,m\le 2\times 10^9, 0\le s[i]\le 2\times 10^9$。

子任务	分数	附加约束条件
$1$	$10$	$m=1$
$2$	$15$	所有 $s[i]$ 相同
$3$	$20$	$n\le 20$
$4$	$25$	$n\le 100$
$5$	$30$	无附加限制