H. Hashing Collision
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Recently, Colin learned how the string hashing algorithm works. Generally speaking, it is used to convert a string into an integer.

The good and widely used way to define the hash of a string $$$s$$$ of length $$$n$$$ (indexed from $$$1$$$) is

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

where $$$p$$$ and $$$m$$$ are some chosen, positive numbers. It is called a polynomial rolling hash function.

But Colin doesn't understand how to choose appropriate $$$p$$$ and $$$m$$$, so he often encounters hashing collision problems. Consider two substrings $$$s_1,s_2$$$ of the string $$$s$$$ such that $$$s_1\not= s_2$$$ but $$$hash(s_1)=hash(s_2)$$$ holds; then we say that there is a hashing collision between $$$s_1$$$ and $$$s_2$$$.

Now given a string $$$s$$$ of length $$$n$$$, and two integers $$$p$$$ and $$$m$$$ chosen by Colin. He wants to know how many ways there are to choose integers $$$l_1,r_1,l_2,r_2$$$ satisfying $$$1\le l_1\le r_1\le n, 1\le l_2\le r_2\le n$$$, and there is a hashing collision between $$$s[l_1,r_1]$$$ and $$$s[l_2,r_2]$$$

Input

The first line contains three integers $$$n, p, m\ (1\le n\le 3000, 1\le p,m\le 2\times 10^9)$$$.

The second line contains $$$n$$$ integers $$$s[1],s[2],\dots,s[n]\ (0\le s[i]\le 2\times 10^9)$$$, the $$$i$$$-th integer represents the value of the $$$i$$$-th character of string $$$s$$$.

Output

A single integer represents the answer.

Examples
Input
4 2 6
1 2 1 2
Output
4
Input
4 2 5
1 2 1 2
Output
10
Note

For the first example, the hashing results of each substring:

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

The ways to select parameters in the answer:

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