Recientemente, Colin aprendió cómo funciona el algoritmo de hash de cadenas. En términos generales, se utiliza para convertir una cadena en un entero.

Una forma buena y ampliamente utilizada de definir el hash de una cadena $s$ de longitud $n$ (indexada desde 1) es

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

donde $p$ y $m$ son números positivos elegidos. Esta se denomina función de hash rodante polinomial.

Pero Colin no entiende cómo elegir valores apropiados para $p$ y $m$, por lo que a menudo se encuentra con problemas de colisión de hash. Considere dos subcadenas $s_1, s_2$ de la cadena $s$ tales que $s_1 \neq s_2$ pero se cumple $hash(s_1) = hash(s_2)$; entonces decimos que hay una colisión de hash entre $s_1$ y $s_2$.

Ahora, dada una cadena $s$ de longitud $n$, y dos enteros $p$ y $m$ elegidos por Colin. Él quiere saber cuántas formas hay de elegir enteros $l_1, r_1, l_2, r_2$ que satisfagan $1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n$, y que exista una colisión de hash entre $s[l_1, r_1]$ y $s[l_2, r_2]$.

Entrada

La primera línea contiene tres enteros $n, p, m$ ($1 \le n \le 3000, 1 \le p, m \le 2 \times 10^9$).

La segunda línea contiene $n$ enteros $s[1], s[2], \ldots, s[n]$ ($0 \le s[i] \le 2 \times 10^9$), donde el $i$-ésimo entero representa el valor del $i$-ésimo carácter de la cadena $s$.

Salida

Un solo entero que representa la respuesta.

Ejemplos

Entrada 1

4 2 6
1 2 1 2

Salida 1

4

Ejemplos

Entrada 2

4 2 5
1 2 1 2

Salida 2

10

Nota

Para el primer ejemplo, los resultados del hash de cada subcadena:

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

Las formas de seleccionar los parámetros en la respuesta:

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