最近，Colin 学习了字符串哈希算法的原理。一般来说，它用于将字符串转换为整数。

对于长度为 $n$（下标从 1 开始）的字符串 $s$，一种常用且效果良好的哈希定义方式为

$$hash(s) = \left(s[1] + s[2] \cdot p + s[3] \cdot p^2 + \ldots + s[n] \cdot p^{n-1}\right) \bmod m = \left(\sum_{i=0}^{n-1} s[i + 1] \cdot p^i\right) \bmod m$$

其中 $p$ 和 $m$ 是选取的某些正整数。这被称为多项式滚动哈希函数。

但 Colin 不知道该如何选择合适的 $p$ 和 $m$，因此他经常遇到哈希冲突问题。考虑字符串 $s$ 的两个子串 $s_1, s_2$，若满足 $s_1 \neq s_2$ 但 $hash(s_1) = hash(s_2)$ 成立，则我们称 $s_1$ 与 $s_2$ 之间发生了哈希冲突。

现在给定一个长度为 $n$ 的字符串 $s$，以及 Colin 选取的两个整数 $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]$ 之间发生哈希冲突。

输入格式

第一行包含三个整数 $n, p, m$（$1 \le n \le 3000, 1 \le p, m \le 2 \times 10^9$）。

第二行包含 $n$ 个整数 $s[1], s[2], \ldots, s[n]$（$0 \le s[i] \le 2 \times 10^9$），第 $i$ 个整数表示字符串 $s$ 的第 $i$ 个字符的值。

输出格式

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

样例

输入格式 1

4 2 6
1 2 1 2

输出格式 1

4

样例

输入格式 2

4 2 5
1 2 1 2

输出格式 2

10

说明

对于第一个样例，各个子串的哈希结果如下：

$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$