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~ với ~1≤i≤j≤n~, tổng dãy con liên tiếp ~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:

Dòng 1: hai số nguyên dương ~n,k~ (~n≤10^6,k≤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 |≤10^9,i=1…n~) là giá trị của các phần tử của dãy ban đầu.

Kết quả:

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ụ

Input

5 3

2 -6 1 9 -3

Output

7

Giới hạn:

• Subtask1: có 5/25 test tương ứng 1 điểm với ~n≤10^2~;
• Subtask2: có 15/25 test tương ứng 3 điểm với ~n≤10^3~;
• Subtask3: có 5/25 test tương ứng 1 điểm với ~n≤10^6~.