~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