Divisible Pair Sums

Given an array A of N integers and a positive integer K, your task is to count the number of pairs (i, j) satisfying \(1 \leq i < j \leq N\) such that the sum \(A_i + A_j\) is divisible by \(K\). The problem involves computing the frequencies of remainders modulo \(K\) and then using combinatorial methods to count valid pairs.

Input: The first line contains two integers, \(N\) and \(K\). The second line contains \(N\) space-separated integers representing the array \(A\).

Output: Output a single integer representing the number of valid pairs.

Constraints:

• \(1 \leq N \leq 10^5\)
• \(1 \leq K \leq 10^5\)
• \(0 \leq A_i \leq 10^9\)

Be careful to handle special cases such as when the remainder is zero or when \(K\) is even.

inputFormat

The input is read from standard input (stdin) and consists of two parts:

1. The first line contains two integers \(N\) and \(K\), where \(N\) is the number of elements in the array and \(K\) is the divisor.
2. The second line contains \(N\) space-separated integers representing the array \(A\).

Example:

5 2
1 3 2 6 4

outputFormat

The output is a single integer printed to standard output (stdout) that represents the number of pairs \((i,j)\) such that \(A_i + A_j\) is divisible by \(K\).

Example:

4

## sample

5 2
1 3 2 6 4

4