Cho một mảng số nguyên ~a~ gồm ~n~ phần tử ( ~1 \le n \le 3 \times 10^4~, ~-10^4 \le a_i \le 10^4~).

Một số nguyên dương ~k~ (~2 \le k \le 10^4~).

Hãy đếm số lượng đoạn con khác rỗng của mảng sao cho tổng các phần tử trong đoạn con đó chia hết cho ~k~. Một đoạn con là một dãy các phần tử liên tiếp trong mảng.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Output

• In ra số lượng đoạn con khác rỗng có tổng chia hết cho ~k~.

Ví dụ

Sample Input

6 5
4 5 0 -2 -3 1

Sample Output

7

Sample Input

19
5

Sample Output

0