Hashing Collision

题号：NC295163
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Recently Colin learned how the string hashing algorithm works. Generally speaking, it is 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 betweem $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 are there 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]$ .

输入描述:

The first line contains three integers .

The second line contains  integers , the -th integer represents the value of the -th character of string .

输出描述:

A single integer represents the answer.

示例1

输入

复制

4 2 6
1 2 1 2

输出

复制

说明

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

















The ways to select parameters in the answer:

1. 

2. 

3. 

4.

示例2

输入

复制

4 2 5
1 2 1 2

输出

复制