配点 : $400$ 点

問題文

$N$ 個の箱が左右一列に並んでおり、左から $i$ 番目の箱には $A_i$ 個のお菓子が入っています。

あなたは、連続したいくつかの箱からお菓子を取り出して $M$ 人の子供たちに均等に配りたいと考えています。

そこで、以下を満たす組 $(l, r)$ の総数を求めてください。

• $l, r$ はともに整数であり $1 \leq l \leq r \leq N$ を満たす
• $A_l + A_{l+1} + ... + A_r$ は $M$ の倍数である

制約

• 入力は全て整数である
• $1 \leq N \leq 10^5$
• $2 \leq M \leq 10^9$
• $1 \leq A_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_1$ $A_2$ $...$ $A_N$

出力

条件を満たす組 $(l, r)$ の総数を出力せよ。

出力の際には、出力が $32$ ビットの整数型に収まらない可能性があることに注意せよ。

3 2
4 1 5

3

各組 $(l, r)$ に対する和 $A_l + A_{l+1} + ... + A_r$ は次のとおりであり、このうち $3$ つが $2$ の倍数です。

• $(1, 1)$ に対する和: $4$
• $(1, 2)$ に対する和: $5$
• $(1, 3)$ に対する和: $10$
• $(2, 2)$ に対する和: $1$
• $(2, 3)$ に対する和: $6$
• $(3, 3)$ に対する和: $5$

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

6

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

25