Cho số nguyên dương \(n\) và dãy số \(a\) gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\). Một dãy con liên tiếp của dãy số \(a\) có dạng \(a_i, a_{i+1}, …, a_j\) với \(1 \leq i \leq j \leq n\), tổng của dãy con liên tiếp \(a_i, a_{i+1}, …, a_j\) là \(a_i, a_{i+1}, …, a_j\)
Em hãy đếm số lượng dãy con liên tiếp của dãy số a đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương \(k\).

INPUT

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(k\) \((1 \leq n \leq 10^6, 1 \leq k \leq 10^9)\). Các số trên cùng một dòng được phân tách bởi ít nhất một khoảng trắng.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((|a_i| \leq 10^9, 1 \leq i \leq n)\). Các số trên cùng một dòng được phân tách bởi ít nhất một khoảng trắng.

Output

• In ra một số duy nhất là số lượng dãy con có tổng các phần tử chia hết cho \(k\).

Example

5 3
2 -6 1 9 -3

7

Ràng buộc

• Subtask \(1\) (\(50\%\) số điểm): Có \(n\) \((n \leq 10^3)\),
• Subtask \(2\) (\(50\%\) số điểm): Có \(n\) \((n \leq 10^6)\)