Given an integer array nums and an integer d, count the number of index triplets (i, j, k) such that $i < j < k$ and the sum nums[i] + nums[j] + nums[k] is divisible by d.

Return the total number of such triplets.

Constraints:

• $1 \leq$ nums.length $\leq 1000$

• $1 \leq$ nums[i] $\leq 10^9$

• $1 \leq$ d $\leq 10^9$

Input: nums = [1, 2, 4]-List[int], d = 7-int
Output: 1-int
Explanation: There is only one triplet (0, 1, 2), with sum 1 + 2 + 4 = 7, and 7 % 7 = 0, so it is divisible by d.

Input: nums = [2, 5, 9, 14, 20]-List[int], d = 4-int
Output: 3-int
Explanation: Checking the index triplets, (0, 3, 4) sums to 36 (36 % 4 = 0), (0, 1, 2) sums to 16 (16 % 4 = 0), and (1, 2, 3) sums to 28 (28 % 4 = 0), while (0, 1, 3) = 21, (0, 2, 3) = 25, (1, 2, 4) = 34, (1, 3, 4) = 39, (0, 1, 4) = 27, and (2, 3, 4) = 43 are not divisible by 4. So there are 3 valid triplets: (0,1,2), (1,2,3), and (0,3,4).

Input: nums = [6, 10, 15, 21, 28, 36]-List[int], d = 1-int
Output: 20-int
Explanation: Any integer sum is divisible by 1, so with n = 6, the number of index triplets is C(6, 3) = 20, and the answer is 20.

Input: nums = [1000000000, 999999999, 999999998, 7, 11, 13, 17]-List[int], d = 1000000000-int
Output: 0-int
Explanation: A sum is divisible by 10^9 only if its remainder modulo 10^9 is 0. None of the possible triplet sums in this array produce a remainder of 0, so there are no valid triplets.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.