SumDivK

Time limit: 1.5s Memory limit: 128MB Input: Output:

Task

An array is given with NN elements and one number RR. Find out in how many ways we can choose 33 positions from array i j ki \ j \ k so that i<j<ki < j < k and the sum of the values from array, from this 33 distinct positions, will be multiple of RR.

Input data

On the first line you will find 22 integers, NN and RR.
On the second line you will find NN numbers, representing the given array.

Output data

On the first line will find a single integer, the number of ways to choose 33 distinct positions in the array so that their sum is multiple of RR. As the number may pass the long long limit, we will display the number modulo 1 000 000 0071 \ 000 \ 000 \ 007.

Constraints and clarifications

  • 2NR10 000 0002 \leq N \cdot R \leq 10 \ 000 \ 000
  • 2R10 000 000N2 \leq R \leq \frac{10 \ 000 \ 000}{N}
  • The values from array 2631\leq 2^{63}-1
  • For 3030 points N,R1 000N, R \leq 1 \ 000

Comment

Due to the very large input data, we recommend using the following lines at the beginning of the main() function in the C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Example

stdin

5 3
1 2 3 4 5

stdout

4

Log in or sign up to be able to send submissions!