Counting Triplets (Sum Divisible by d)

Given an integer array, count the triplets with strictly increasing indices whose three values sum to a multiple of d.

This site uses a standard input/output protocol.

输入格式

The first line contains n d; the second line contains n integers. 3≤n≤1000, 1≤arr[i]≤10^9, 2≤d≤10^6.

输出格式

Output the number of qualifying index triplets.

样例 1

输入：

4 3
2 3 1 6

输出：

2

样例 2

输入：

3 3
1 1 1

输出：

1

样例 3

输入：

4 5
1 2 4 8

输出：

0