Cho dãy số nguyên gồm ~N~ phần tử ~a_1,a_2,…,a_N~ và số nguyên dương ~k~

Yêu cầu:

Đếm số lương đoạn con liên tiếp có tổng chia hết cho K. Hay nói cách khác bạn hãy đếm số lượng cặp (~i,j~) mà ~1≤i≤j≤N~ và (~a_i+a_{(i+1)}+⋯+a_j )⋮K~.

Input:

Cho trong tệp IDP2004c.INP

• Dòng đầu chứa số nguyên dương ~N~ và ~K~ (~N,K≤10^5~ );
• Dòng thứ hai chứa ~N~ số nguyên ~a_1,a_2,…,a_N~ (~|a_i |≤10^5~ ).

  Output:

Ghi ra tệp IDP2004c.OUT số lượng đoạn con thỏa mãn

Ví dụ:

IDP2004D.INP

5 3
-2 3 5 -4 1

IDP2004D.OUT

4