Count Subarrays with Sum Divisible by P

You are given an array of n integers and a prime number p. Your task is to count the number of distinct subarrays (i.e. contiguous segments) whose sum is divisible by p.

Let the array be \(a_1, a_2, \ldots, a_n\). A subarray \(a_i, a_{i+1}, \ldots, a_j\) is considered valid if

\(\sum_{k=i}^{j} a_k \equiv 0 \pmod{p}\)

It is recommended to use a prefix sum approach along with modular arithmetic to efficiently solve the problem.

inputFormat

The input is given in stdin and consists of two lines:

• The first line contains two integers n (the number of elements) and p (a prime number).
• The second line contains n space-separated integers representing the array.

\(1 \leq n \leq 10^5\) and the absolute values of the integers are up to \(10^9\).

outputFormat

Output a single integer on a new line, which is the number of subarrays whose sum is divisible by p.

The output should be written to stdout.

## sample

5 3
1 -2 3 4 -6

4