Cho mảng các số tự nhiên ~A = [a_1, a_2, a_3, \dots, a_n]~ và số nguyên ~k~. Cần tìm cặp số ~(l, r)~ sao cho ~l \le r~ và tổng các số trên mảng ~A~ từ vị trí ~l~ đến ~r~ chia hết cho ~k~.

Input

Dòng đầu tiên chứa các số nguyên ~n~, ~k~ ~(1 \le n \le 200000, 2 \le k \le 10^9)~.

Dòng thứ hai chứa các số nguyên ~a_1, a_2, a_3, \dots, a_n~ ~(1 \le a_i \le 10^9)~.

Output

In ra số lượng cặp số ~(l, r)~ thỏa yêu cầu bài toán.

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

6