Đoạn chia hết cho M

Time limit: 1.0s , Memory limit: 256M , Points: 20 (partial)

Cho một dãy $N$ $N$ số nguyên $a_1, a_2,\ldots, a_n$ $a_{1}, a_{2}, \dots, a_{n}$ . Bi muốn đếm xem trong dãy số trên có bao nhiêu đoạn mà tổng các số trong đoạn chia hết cho số nguyên dương $M$ $M$ cho trước. Đoạn được định nghĩa là dãy $a_l,\ldots, a_r$ $a_{l}, \dots, a_{r}$ thỏa $1\le l \le r \le n$ $1 \leq l \leq r \leq n$ .

Hãy lập trình giúp Bi.

Input

Dòng đầu tiên chứa hai số nguyên dương $N, M$ $N, M$ thỏa $1 \le N \le 10^5; 2 \le M \le 10^9$ $1 \leq N \leq 10^{5}; 2 \leq M \leq 10^{9}$ .

Dòng tiếp theo chứa các số nguyên $a_i$ $a_{i}$ thỏa $1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$ .

Output

In ra số cần tìm.

Samples

Sample Input 1

Copy

3 2
4 1 5

Sample Output 1

Copy

Note

đoạn $[1..1]$ $[1. .1]$ có tổng bằng $4$ $4$ chia hết cho $2$ $2$ , đoạn $[1..3]$ $[1. .3]$ có tổng bằng $10$ $10$ chia hết cho $2$ $2$ , đoạn thứ ba $[2..3]$ $[2. .3]$ có tổng bằng $6$ $6$ thỏa điều kiện chia hết cho $2$ $2$