D - Candy Distribution

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

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

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

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

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

制約

  • 入力は全て整数である
  • 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 ビットの整数型に収まらない可能性があることに注意せよ。


入力例 1

3 2
4 1 5

出力例 1

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

入力例 2

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

出力例 2

6

入力例 3

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

出力例 3

25

Score : 400 points

Problem Statement

There are N boxes arranged in a row from left to right. The i-th box from the left contains A_i candies.

You will take out the candies from some consecutive boxes and distribute them evenly to M children.

Such being the case, find the number of the pairs (l, r) that satisfy the following:

  • l and r are both integers and satisfy 1 \leq l \leq r \leq N.
  • A_l + A_{l+1} + ... + A_r is a multiple of M.

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 10^5
  • 2 \leq M \leq 10^9
  • 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_N

Output

Print the number of the pairs (l, r) that satisfy the conditions.

Note that the number may not fit into a 32-bit integer type.


Sample Input 1

3 2
4 1 5

Sample Output 1

3

The sum A_l + A_{l+1} + ... + A_r for each pair (l, r) is as follows:

  • Sum for (1, 1): 4
  • Sum for (1, 2): 5
  • Sum for (1, 3): 10
  • Sum for (2, 2): 1
  • Sum for (2, 3): 6
  • Sum for (3, 3): 5

Among these, three are multiples of 2.


Sample Input 2

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

Sample Output 2

6

Sample Input 3

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

Sample Output 3

25