Récemment, Colin a appris le fonctionnement de l'algorithme de hachage de chaînes. De manière générale, il sert à convertir une chaîne en un entier.

Une méthode efficace et largement utilisée pour définir le hachage d'une chaîne $s$ de longueur $n$ (indexée à partir de 1) est :

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

où $p$ et $m$ sont des nombres positifs choisis. On appelle cela une fonction de hachage polynomial roulant.

Mais Colin ne comprend pas comment choisir des $p$ et $m$ appropriés, de sorte qu'il rencontre souvent des problèmes de collision de hachage. Considérons deux sous-chaînes $s_1, s_2$ de la chaîne $s$ telles que $s_1 \neq s_2$ mais $hash(s_1) = hash(s_2)$ ; nous disons alors qu'il y a une collision de hachage entre $s_1$ et $s_2$.

Étant donnés une chaîne $s$ de longueur $n$, ainsi que deux entiers $p$ et $m$ choisis par Colin, il souhaite savoir de combien de manières il est possible de choisir les entiers $l_1, r_1, l_2, r_2$ satisfaisant $1 \le l_1 \le r_1 \le n, 1 \le l_2 \le r_2 \le n$, de telle sorte qu'il y ait une collision de hachage entre $s[l_1, r_1]$ et $s[l_2, r_2]$.

Entrée

La première ligne contient trois entiers $n, p, m$ ($1 \le n \le 3000, 1 \le p, m \le 2 \times 10^9$).

La deuxième ligne contient $n$ entiers $s[1], s[2], \ldots, s[n]$ ($0 \le s[i] \le 2 \times 10^9$), où le $i$-ième entier représente la valeur du $i$-ième caractère de la chaîne $s$.

Sortie

Un unique entier représentant la réponse.

Exemples

Exemples

Entrée 1

4 2 6
1 2 1 2

Sortie 1

4

Exemples

Entrée 2

4 2 5
1 2 1 2

Sortie 2

10

Remarque

Pour le premier exemple, les résultats de hachage de chaque sous-chaîne sont :

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

Les façons de choisir les paramètres dans la réponse sont :

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