Problem Statement

Divisible Triplets You are given an array arr of n integers and a positive integer d . Count the triplets of positions (i, j, k) with 0 <= i < j < k < n whose values add up to a multiple of d , that is (arr[i] + arr[j] + arr[k]) % d == 0 . Report how many such triplets exist. Input Format The first line contains an integer n , the size of arr . Each of the next n lines contains one integer arr[i] . The last line contains the integer d . Output Format Print a single integer — the number of triplets of positions whose values sum to a multiple of d . Constraints 3 <= n <= 15000 1 <= arr[i] <= 10^9 2 <= d <= 1000 The answer can reach C(15000, 3) = 562459985000 , which does not fit in a 32-bit signed integer, so use long long in C++ and long in Java. Examples Example 1 Input: 5 3 3 4 7 8 5 Output: 3 Explanation: with arr = [3, 3, 4, 7, 8] and d = 5 the qualifying position triplets are (0, 1, 2) with 3 + 3 + 4 = 10 , (0, 2, 4) with 3 + 4 + 8 = 15 , and (1, 2, 4)