Đếm đoạn chia hết

Bạn An có một hàng gồm \(N\) chiếc hộp, mỗi hộp chứa một số viên kẹo. Số viên kẹo trong hộp thứ \(i\) là \(a_i\).

An muốn chọn ra một đoạn liên tiếp các hộp sao cho tổng số kẹo trong đoạn đó chia hết cho \(K\).

Hãy giúp An đếm xem có bao nhiêu đoạn như vậy.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^5\), \(1 \le K \le 10^9\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i \le 10^9\)).

Output

• In ra một số nguyên — số lượng đoạn con (liên tiếp) có tổng chia hết cho \(K\).

Scoring

• Có \(50\%\) số điểm ứng với \(N \le 1000\).

Sample Input 1

5 3
1 2 3 2 2

Sample Output 1

4