SumDivK

Task

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

Input data

On the first line you will find $2$ integers, $N$ and $R$.
On the second line you will find $N$ numbers, representing the given array.

Output data

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

Constraints and clarifications

• $2 \leq N \cdot R \leq 10 \ 000 \ 000$
• $2 \leq R \leq \frac{10 \ 000 \ 000}{N}$
• The values from array $\leq 2^{63}-1$
• For $30$ points $N, 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