Dãy con có tổng chia hết

Cho dãy số nguyên dương \(a_1, a_2, \ldots, a_n\) và một số nguyên dương \(K\). Hãy đếm xem có bao nhiêu dãy con \(a_i, a_{i+1}, \ldots, a_j\) (\(1 \le i \le j \le n\)) khác nhau có tổng \(a_i + a_{i+1} + \cdots + a_j\) chia hết cho \(K\). Hai dãy con \(a_{i_1}, a_{i_1+1}, \ldots, a_{j_1}\) và \(a_{i_2}, a_{i_2+1}, \ldots, a_{j_2}\) được gọi là khác nhau nếu \(i_1 \ne i_2\) hoặc \(j_1 \ne j_2\).

Input

Đọc từ bàn phím:

• Dòng đầu chứa hai số nguyên dương \(n, K\) (\(n \le 10^5\); \(1 \le K \le 10^9\)) cách nhau một dấu trống.

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\), \(\forall i = 1, 2, \ldots, n\)) cách nhau bằng dấu trống.

Ràng buộc:

• Có \(1\) test thỏa mãn \(n \le 100\).

• Có \(2\) test thỏa mãn \(n \le 5000\).

• Có \(2\) test tiếp theo thỏa mãn \(10^3 < n \le 10^5\); \(K \le 10^6\).

• \(1\) test còn lại không có ràng buộc bổ sung.

Output

Ghi ra màn hình duy nhất một số nguyên là số lượng dãy con tìm được.

Example

Input:

6 2
2 1 2 2 1 3

Output:

9

Note

Tổng tiền tố theo modulo \(2\) là \(P_0, \ldots, P_6 = 0, 0, 1, 1, 1, 0, 1\). Giá trị \(0\) xuất hiện ở các chỉ số \(0, 1, 5\) (tạo \(3\) cặp) và giá trị \(1\) xuất hiện ở các chỉ số \(2, 3, 4, 6\) (tạo \(6\) cặp), tổng cộng \(9\) dãy con có tổng chẵn: \([2]\), \([1,2,2,1]\), \([2,1,2,2,1]\), \([2]\), \([2,2]\), \([2,2,1,3]\), \([2]\), \([2,1,3]\) và \([1,3]\).