最近、Colin は文字列ハッシュアルゴリズムの仕組みを学びました。一般的に、これは文字列を整数に変換するために使用されます。

長さ $n$ の文字列 $s$（インデックスは 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$ は選択された正の整数です。これは多項式ローリングハッシュ関数と呼ばれます。

しかし、Colin は適切な $p$ と $m$ の選び方を理解していないため、しばしばハッシュ衝突の問題に遭遇します。文字列 $s$ の 2 つの部分文字列 $s_1, s_2$ について、$s_1 \neq s_2$ であるにもかかわらず $hash(s_1) = hash(s_2)$ が成り立つとき、$s_1$ と $s_2$ の間でハッシュ衝突が発生しているといいます。

今、長さ $n$ の文字列 $s$ と、Colin が選んだ 2 つの整数 $p$ と $m$ が与えられます。彼は、$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]$ の間でハッシュ衝突が発生するような整数 $l_1, r_1, l_2, r_2$ の選び方が何通りあるかを知りたいです。

入力

1 行目には 3 つの整数 $n, p, m$ ($1 \le n \le 3000, 1 \le p, m \le 2 \times 10^9$) が与えられます。

2 行目には $n$ 個の整数 $s[1], s[2], \ldots, s[n]$ ($0 \le s[i] \le 2 \times 10^9$) が与えられ、$i$ 番目の整数は文字列 $s$ の $i$ 番目の文字の値を表します。

出力

答えを表す整数を 1 行に出力してください。

入出力例

入力 1

4 2 6
1 2 1 2

出力 1

4

入力 2

4 2 5
1 2 1 2

出力 2

10

注記

1 つ目の例について、各部分文字列のハッシュ結果は次のようになります：

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