Phân phát kẹo (Candy Distribution)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Trong $N$ ngày liên tiếp, ngày thứ $i$ có $A_i$ viên kẹo được phát.

Ta chọn một đoạn ngày liên tiếp từ ngày $l$ đến ngày $r$. Tổng số kẹo trong đoạn đó có thể chia đều cho $M$ người nếu và chỉ nếu tổng này chia hết cho $M$.

Hãy đếm số cặp $(l,r)$ với $1\le l\le r\le N$ sao cho

chia hết cho $M$.

Input

• Dòng đầu chứa hai số nguyên $N,M$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In số đoạn ngày liên tiếp có tổng số kẹo chia hết cho $M$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le N\le10^5$

• $2\le M\le10^9$

• $1\le A_i\le10^9$

• Subtask 1 — 20%: $N\le40$

• Subtask 2 — 30%: $N\le3000$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

3 2
4 1 5

Output

3

Giải thích

Với $M=2$ và dãy

ba đoạn có tổng chia hết cho $2$ là:

• $[1,1]$: tổng $4$;
• $[2,3]$: tổng $1+5=6$;
• $[1,3]$: tổng $4+1+5=10$.

Do đó kết quả là $3$.