AT_abc105_d [ABC105D] Candy Distribution

[problemUrl]: https://atcoder.jp/contests/abc105/tasks/abc105_d $ N $ 個の箱が左右一列に並んでおり、左から $ i $ 番目の箱には $ A_i $ 個のお菓子が入っています。 あなたは、連続したいくつかの箱からお菓子を取り出して $ M $ 人の子供たちに均等に配りたいと考えています。 そこで、以下を満たす組 $ (l,\ r) $ の総数を求めてください。 - $ l,\ r $ はともに整数であり $ 1\ \leq\ l\ \leq\ r\ \leq\ N $ を満たす - $ A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r $ は $ M $ の倍数である

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ ... $ $ A_N $

条件を満たす組 $ (l,\ r) $ の総数を出力せよ。 出力の際には、出力が $ 32 $ ビットの整数型に収まらない可能性があることに注意せよ。

### 制約 - 入力は全て整数である - $ 1\ \leq\ N\ \leq\ 10^5 $ - $ 2\ \leq\ M\ \leq\ 10^9 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ ### Sample Explanation 1 各組 $ (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 $