Cho một mảng gồm ~N~ số nguyên, bạn hãy đếm số lượng dãy con liên tiếp khác rỗng có tổng chia hết cho ~K~.

Dữ liệu

Gồm ~2~ dòng:

• Dòng đầu tiên chứa 2 số nguyên ~N~ và ~K~ ~(N \leq 10^5, K \leq 10^9)~.
• Dòng thứ 2 chứa ~N~ số nguyên dương ~a_i~ ~(a_i \leq 10^9)~ phân tách bằng dấu cách.

Kết quả

In ra 1 số nguyên là số đoạn con liên tiếp thỏa mãn đề bài.

Sample Input

8 2
1 2 3 1 4 5 2 7

Sample Output

16

Subtask

• ~20\%~ số test có ~N \le 100~
• ~20\%~ số test tiếp theo có ~N \le 3000~
• ~30\%~ số test tiếp theo có ~K \leq 10^5~
• ~30\%~ số test còn lại không có điều kiện gì thêm