Count Divisible Pairs

You are given an integer n representing the size of an array, an integer k and an array of n integers. Your task is to determine the number of pairs (i, j) such that 1 ≤ i < j ≤ n and the sum a_i + a_j is divisible by k.

In mathematical terms, you need to count the number of pairs (i,j) that satisfy:

$$a_i + a_j \equiv 0 \pmod{k}$$

The problem requires an efficient solution that handles arrays with large numbers and even negative integers. Make sure to consider the edge cases properly.

inputFormat

The first line contains two space-separated integers n and k.

The second line contains n space-separated integers which form the array.

outputFormat

Output a single integer denoting the number of valid pairs where the sum of the pair is divisible by k.

5 3
1 2 3 4 5

4