Problem Description

Given a sequence of length $N$, $A_1, A_2, \cdots A_N$. If the sum of a consecutive subsequence $A_i, A_{i+1}, \cdots A_j (i \le j)$ is a multiple of $K$, then we call the interval $[i, j]$ a $K$-multiple interval.

Can you find how many $K$-multiple intervals there are in the sequence?

Input Format

The first line contains two integers $N$ and $K$ $(1 \le N, K \le 10^5)$.

The next $N$ lines each contain one integer $A_i$ $(1 \le A_i \le 10^5)$.

Output Format

Output one integer, representing the number of $K$-multiple intervals.

5 2
1  
2  
3  
4  
5  

6

Hint

Time limit: 2 seconds, 256M. The 8th Lanqiao Cup 2017.

Translated by ChatGPT 5