output_description: 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.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 A_2 ... A_N
attempt: import math
  
  
  def PC(n, r):
      return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
  
  def ncr(n, r):
      r = min(r, n - r)
      if r == 0:
          return 1
      if r == 1:
          return n
      numerator = [n - r + i + 1 for i in range(r)]
      denominator = [i + 1 for i in range(r)]
      for p in range(2, r + 1):
          pivot = denominator[p - 1]
          if pivot > 1:
              offset = (n - r) % p
              for k in range(p - 1, r, p):
                  numerator[k - offset] /= pivot
                  denominator[k] /= pivot
      result = 1
      for k in range(r):
          if numerator[k] > 1:
              result *= numerator[k]
      return result
  
  
  # kaijou = [0, 1]
  # for i in range(2, 1000):
  #   kaijou.append(kaijou[i - 1] * i)
  
  # print(kaijou[0:10])
  
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  B = []
  j = 0
  for i in A:
      if j == 0:
          B.append(i)
      else:
          B.append(B[j - 1] + i)
      j += 1
  for i in range(len(B)):
      B[i] = B[i] % M
  C = sorted(B)
  anscnt = 0
  samecnt = 1
  for i in range(len(C)):
      if C[i] == 0:
          anscnt += 1
      if i != 0:
          if C[i] == C[i - 1]:
              samecnt += 1
          elif samecnt != 1:
              anscnt += ncr(samecnt, 2)
              samecnt = 1
          if i == len(C) - 1:
              anscnt += ncr(samecnt, 2)
              samecnt = 1
  print(int(anscnt))
  
problem_description: 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.
samples: [{"input": "3 2\n    4 1 5", "output": "3\n    \n\nThe sum A_l + A_{l+1} + ... + A_r for each pair (l, r) is as follows:\n\n  * Sum for (1, 1): 4\n  * Sum for (1, 2): 5\n  * Sum for (1, 3): 10\n  * Sum for (2, 2): 1\n  * Sum for (2, 3): 6\n  * Sum for (3, 3): 5\n\nAmong these, three are multiples of 2.\n\n* * *"}, {"input": "13 17\n    29 7 5 7 9 51 7 13 8 55 42 9 81", "output": "6\n    \n\n* * *"}, {"input": "10 400000000\n    1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000", "output": "25"}]