Count Pairs with Sum Divisible by k

Given an array of integers and an integer \( k \), your task is to count the number of pairs \( (i, j) \) (with \( i < j \)) such that the sum of the two elements is divisible by \( k \). In other words, find the number of pairs \( (a_i, a_j) \) where \( a_i + a_j \equiv 0 \pmod{k} \).

The input is provided via standard input (stdin) and the output should be sent to standard output (stdout). The first line of input contains two integers: \( n \) (the number of elements in the array) and \( k \) (the divisor). The second line contains \( n \) integers representing the elements of the array.

Your solution should be efficient enough to handle edge cases, including arrays with no elements or with elements that produce no valid pairs.

inputFormat

The input begins with a line containing two integers ( n ) and ( k ), separated by a space. Here, ( n ) is the number of elements in the array, and ( k ) is the divisor. The second line contains ( n ) space-separated integers denoting the array elements. Input is read from standard input (stdin).

outputFormat

Output a single integer representing the number of pairs whose sum is divisible by ( k ). The output should be written to standard output (stdout).## sample

6 3
1 2 3 4 5 6

5