최근 Colin은 문자열 해싱 알고리즘이 어떻게 작동하는지 배웠습니다. 일반적으로 이는 문자열을 정수로 변환하는 데 사용됩니다.

길이가 $n$인 문자열 $s$ (1부터 인덱싱됨)의 해시를 정의하는 널리 쓰이는 좋은 방법은 다음과 같습니다.

$$hash(s) = \left(s[1] + s[2] \cdot p + s[3] \cdot p^2 + \dots + 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$의 두 부분 문자열 $s_1, s_2$에 대해 $s_1 \neq s_2$이지만 $hash(s_1) = hash(s_2)$가 성립할 때, $s_1$과 $s_2$ 사이에 해시 충돌이 발생했다고 합니다.

이제 길이가 $n$인 문자열 $s$와 Colin이 선택한 두 정수 $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$를 선택하는 방법이 몇 가지인지 알고 싶어 합니다.

입력

첫 번째 줄에 세 정수 $n, p, m$ ($1 \le n \le 3000, 1 \le p, m \le 2 \times 10^9$)이 주어집니다.

두 번째 줄에 $n$개의 정수 $s[1], s[2], \dots, s[n]$ ($0 \le s[i] \le 2 \times 10^9$)이 주어지며, $i$번째 정수는 문자열 $s$의 $i$번째 문자의 값을 나타냅니다.

출력

답을 나타내는 단일 정수를 출력합니다.

예제

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