Remainder Subarray Count

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$. Count the contiguous intervals whose sum is divisible by $M$.

An interval is a pair $(i, j)$ with $1 \le i \le j \le N$, and it covers $A_i$ through $A_j$. Two intervals count as different when they differ in $i$ or in $j$.

The first line contains $N$ and $M$, separated by a space. ($1 \le N \le 10^6$, $2 \le M \le 10^3$)

The second line contains the $N$ numbers of the sequence $A_1, A_2, \dots, A_N$, separated by spaces. ($0 \le A_i \le 10^9$)

Print the number of intervals that satisfy the condition on the first line.