Cho số nguyên dương ~n~ và dãy số ~a~ gồm ~n~ số nguyên ~a_1, a_2, \dots, 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}, \dots, a_j~ với ~1 \le i \le j \le n~, tổng của dãy con liên tiếp ~a_i, a_{i+1}, \dots, a_j~ là ~a_i + a_{i+1} + \dots + a_j~.

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~.

Yêu cầu: Hãy xác định số lượng dãy con liên tiếp có tổng các phần tử chia hết cho ~k~.

Input

• Dòng 1 ghi 2 số nguyên dương ~n~ và ~k~ (~n \le 10^6~, ~k \le 10^9~).
• Dòng 2 ghi lần lượt các số nguyên ~a_1, a_2, \dots, a_n~ (~|a_i| \le 10^9~, ~i=1 \dots n~).

Output

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

Sample Input 1

5 3 
2 -6 1 9 -3

Sample Output 1

7