Недавно Колин узнал, как работает алгоритм хеширования строк. В целом он используется для преобразования строки в целое число.

Хорошим и широко распространенным способом определения хеша строки $s$ длины $n$ (с нумерацией с 1) является

$$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$ — некоторые выбранные положительные числа. Такая функция называется полиномиальной хеш-функцией.

Но Колин не понимает, как правильно выбирать $p$ и $m$, поэтому часто сталкивается с коллизиями хешей. Рассмотрим две подстроки $s_1, s_2$ строки $s$ такие, что $s_1 \neq s_2$, но выполняется равенство $hash(s_1) = hash(s_2)$; в этом случае говорят, что между $s_1$ и $s_2$ произошла коллизия хешей.

Дана строка $s$ длины $n$ и два целых числа $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$-е число обозначает значение $i$-го символа строки $s$.

Выходные данные

Выведите одно целое число — ответ на задачу.

Примеры

Входные данные 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$