\(N\) коробок з цукерками розташовані в ряд зліва направо. \(i\)-а коробка містить \(A_i\) цукерок.

Ви дістанете цукерки з кількох послідовних коробок і рівномірно розподілите їх між \(М\) дітьми. Хіба таке завжди можна зробити?

Знайдіть кількість таких пар (\(l,r\)), що відповідають таким вимогам:

• \(l\) і \(r\) є цілими числами і задовольняють умову (\(1 \le l \le r \le N\))

• сума \(A_l + A_{l+1} +...+ A_r\) є кратна \(М\)

Формат вхідних даних

Перший рядок містить цілі числа \(N,M\) (\(1 \le N \le 10^5\), \(1 \le M \le 10^9\)).

Наступний рядок містить \(A_1, A_2, ... A_N\) (\(1 \le A_i \le 10^9\)) ​

Формат вихідних даних

Виведіть кількість різних пар (\(l,r\)), що задовільняють описані вимоги.

Приклад вхідних даних

3 2
4 1 5

Приклад вихідних даних

3