Đoạn con chia hết cho M

Cho dãy số nguyên không âm \(a_1, a_2, \dots, a_n\) và số nguyên dương \(M\). Hãy đếm số cặp \((l, r)\) với \(1 \le l \le r \le n\) sao cho tổng \(a_l + a_{l+1} + \dots + a_r\) chia hết cho \(M\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, M\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le M \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^9\)).

Output

• Một số nguyên là số đoạn con có tổng chia hết cho \(M\).

Subtask

• \(30\%\) số test: \(n \le 300\).
• \(30\%\) số test: \(n \le 5000\).
• \(40\%\) số test: không có ràng buộc gì thêm.

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

7

Notes

Có \(7\) đoạn thỏa mãn: \([1, 2]\), \([3, 3]\), \([1, 3]\), \([2, 4]\), \([4, 5]\), \([3, 5]\), \([1, 5]\).