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~