Cho một dãy ~N~ số nguyên ~a_1, a_2,\ldots, 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~ cho trước. Đoạn được định nghĩa là dãy ~a_l,\ldots, a_r~ thỏa ~1\le l \le r \le 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~ thỏa ~1 \le N \le 10^5; 2 \le M \le 10^9~.

Dòng tiếp theo chứa các số nguyên ~a_i~ thỏa ~1 \le a_i \le 10^9~.

Output

In ra số cần tìm.

Samples

Sample Input 1

3 2
4 1 5

Sample Output 1

3

Note

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