Given a sequence of integers and a nonnegative integer , count the number of pairs that satisfy the following two conditions: , and .
- The first line contains integers and , separated by a space.
- The second line contains integers, which denotes .
- In of the test cases, .
- The output contains an integer, which denotes the number of pairs that satisfy the two conditions.
- If the output is smaller than , please keep it as is. Otherwise, output the number mod .
Sample Input 1
5 6 1 2 3 4 5
Sample Output 1
Sample Input 2
5 12 3 6 8 2 8
Sample Output 2
Explanation: In Sample 1, among the pairs, , , , , , satisfy the conditions. In Sample 2, , , , , , , satisfy the conditions.