Đoạn chia hết (Divisible Subarrays)

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

Đề bài

Cho dãy gồm $N$ số nguyên

và một số nguyên dương $K$.

Một đoạn con liên tiếp $[L,R]$ với $1 \le L \le R \le N$ được gọi là đoạn chia hết nếu tổng các phần tử trên đoạn đó chia hết cho $K$, tức là

Hãy đếm số cặp chỉ số $(L,R)$ thỏa mãn điều kiện trên.

Input

• Dòng đầu chứa hai số nguyên dương $N$ và $K$, cách nhau bởi một dấu cách.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$, các số cách nhau bởi dấu cách.

Output

In ra một số nguyên duy nhất là số đoạn con liên tiếp có tổng chia hết cho $K$.

Subtask

• Subtask 1 — 10%: $1 \le N \le 2\cdot10^5$; $K=1$; $|A_i| \le 10^9$.
• Subtask 2 — 15%: $1 \le N \le 300$; $1 \le K \le 2\cdot10^5$; $|A_i| \le 10^9$.
• Subtask 3 — 25%: $1 \le N \le 5000$; $1 \le K \le 2\cdot10^5$; $|A_i| \le 10^9$.
• Subtask 4 — 50%: $1 \le N \le 2\cdot10^5$; $1 \le K \le 2\cdot10^5$; $|A_i| \le 10^9$.

Ví dụ

Input

5 3
1 2 3 4 2

Output

7

Giải thích

Có $7$ đoạn con có tổng chia hết cho $3$:

• $[1,2]$: $1+2=3$;
• $[1,3]$: $1+2+3=6$;
• $[1,5]$: $1+2+3+4+2=12$;
• $[2,4]$: $2+3+4=9$;
• $[3,3]$: $3$;
• $[3,5]$: $3+4+2=9$;
• $[4,5]$: $4+2=6$.

Vì vậy kết quả cần in ra là $7$.