Get Triplet Count

Given daily stock prices arr and a positive integer d, count the triplets (i,j,k) of distinct indices with i<j<k such that arr[i]+arr[j]+arr[k] is divisible by d.

输入格式

The first line contains n and d, and the second line contains n integers arr. Ranges on this site: 0≤n≤2000, 1≤d≤1000, -2³¹≤arr[i]≤2³¹−1. The bounds n≤2000 and d≤1000 and the allowance for negative numbers were added by this site for the OJ; the original site did not give complete constraints.

输出格式

Output the number of index triplets that satisfy the condition.

样例 1

输入：

5 5
3 3 4 7 8

输出：

3

样例 2

输入：

0 1

输出：

0

样例 3

输入：

1 1
1

输出：

0

样例说明

This problem follows OAMaster's explicit reference to LeetCode 2964 and counts distinct index combinations; triplets with equal values but different indices are still considered different.