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$