Cho số nguyên dương \(n\) và dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2,..., a_n\). Một dãy con liên tiếp của dãy số \(a\) có dạng \(a_i, a_{i+1},..., a_j\) là \(a_i + a_{i+1} + ... +a_j\).

Em hãy đếm số lượng dãy con liên tiếp của dãy số \(a\) đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương \(k\).

Dữ liệu vào:

• Dòng 1: hai số nguyên dương \(n, k\) \((n \le 10^6, k \le 10^9)\) cách nhau một khoảng trống.
• Dòng 2: ghi \(n\) số nguyên \(a_1, a_2, ..., a_n\) \((|a_i| \le 10^9, i = 1...n)\) là giá trị của các phần tử của dãy ban đầu.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là số lượng dãy con có tổng các phần tử chia hết cho \(k\).

Ví dụ:

Giới hạn:

• Subtask 1: Có 5/25 test ứng với 1 điểm \(n \le 10^2\)
• Subtask 2: Có 5/25 test ứng với 1 điểm \(n \le 10^3\)
• Subtask 3: Có 5/25 test ứng với 1 điểm \(n \le 10^6\)