Remainder Subarray Count

Interview

Time limit1sMemory limit256 MB

Summary

Count contiguous intervals whose sum is divisible by M using prefix remainder frequencies.

Level: Medium4 of 10
Topics: Prefix sum, Hash map
Solved: No attempts yet

Problem

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$ .

Input

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$ )

Output

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

Examples3

Example 1
Input
```
5 3
1 2 3 1 2
```
Expected output
```
7
```
Example 2
Input
```
3 5
1 2 3
```
Expected output
```
1
```
Example 3
Input
```
1 2
4
```
Expected output
```
1
```