K-Multiple Intervals

Given a sequence of N integers, \(A_1, A_2, \ldots, A_N\), we define an interval \([i,j]\) (with \(1 \le i \le j \le N\)) to be a K-multiple interval if the sum of the elements in the interval, \(A_i + A_{i+1} + \cdots + A_j\), is a multiple of \(K\) (i.e. it is divisible by \(K\)).

Your task is to calculate the total number of K-multiple intervals in the sequence.

Note: Use appropriate algorithms to handle large input sizes efficiently.

inputFormat

The input consists of two lines. The first line contains two space-separated integers (N) and (K). The second line contains (N) space-separated integers representing the sequence (A_1, A_2, \ldots, A_N).

outputFormat

Output a single integer, which is the number of intervals ([i,j]) such that the sum (A_i + A_{i+1} + \cdots + A_j) is a multiple of (K).

sample

5 3
1 2 3 4 1

4