Sau khi tới nơi có kho báu, BabyOrange tưởng rằng họ đã có kho báu nhưng thực chất lại không hề như vậy. Chỉ là một khu rừng hoang sơ với một con đường nhỏ giữa khu rừng. Vì tò mò, họ quyết định đi trên con đường đó. Trên đường, cậu phát hiện có một bức tường chặn giữa đường, giữa bức tường có một cánh cửa bị khóa. Cậu còn phát hiện trên bức tường có khắc một dãy \(N\) con số và một con số \(S\).
Đột nhiên, một dòng chữ trên bức tường bỗng phát sáng: "Muốn bước qua bức tường, cần tìm ra mật mã để mở phong ấn, mật mã chính là tổng số lượng các đoạn liên tiếp trên phiến đã có tổng chia hết cho \(S\)"
Hãy giúp BabyOrange giải mật mã nhé
Lưu ý: Dãy số có thể có số âm 🙂

Input

• Dòng đầu chứa 2 số nguyên \(N\) \((1 \le n \le 200000)\) và \(S\) \((-10^{14} \le S \le 10^{14})\)
• Dòng thứ hai gồm n số nguyên dương \((-10^9 \le {n_i} \le 10^9)\)

Output

• Gồm một số chính là kết quả đề bài

Example

5 3
1 2 -1 4 2

4

8 5
4 1 3 -8 5 -2 7 3

13