CodeEff/ECCO huggingface dataset:
# Original solution
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))

from collections import defaultdict
d = defaultdict(int)

ans = 0
for i in range(N-1, -1, -1):
    b = defaultdict(int)

    b[ A[i] % M ]  += 1
    for dkey in list(d.keys()):
        b[ (A[i] + dkey)%M ] +=   d[dkey] # b[A[i]] + d[dkey] 
    ans += b[0]

    d = b

#print("ans: ", ans)
# print(d)
print(ans)
    
    


# Optimized solution
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))

from collections import defaultdict
# d = defaultdict(int)
d = defaultdict(list)
# d = defaultdict(set)
# d = {}


B = [0] * (N+1)
B[0] = 0 
# B[1] = A[0]
for i in range(0,N):
    B[i+1] = A[i]
    B[i+1] += B[i]

# print(B)


for i in range(0,N+1):
    d[ B[i] % M] += [i]
    # d[ B[i] % M] |= set([i])
# print(d)
# exit(0)

from bisect import bisect_left

ans = 0
for i in range(0,N+1):
    m = B[i] % M 
    # print(d[m])
    ans += bisect_left( d[m], i)
    # print("{i:3d}: d[{m}]: {d}  bisect({i}): {bi}".format(m=m, d=d[m], i=i, bi=bisect_left(d[m], i)))

    
    
# for i in range(N-1, -1, -1):

print(ans)
# Original solution
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))

from collections import defaultdict
# d = defaultdict(int)
d = defaultdict(list)
# d = defaultdict(set)
# d = {}


B = [0] * (N+1)
B[0] = 0 
# B[1] = A[0]
for i in range(0,N):
    B[i+1] = A[i]
    B[i+1] += B[i]

# print(B)


for i in range(0,N+1):
    d[ B[i] % M] += [i]
    # d[ B[i] % M] |= set([i])
# print(d)
# exit(0)

from bisect import bisect_left

ans = 0
for i in range(0,N+1):
    m = B[i] % M 
    # print(d[m])
    ans += bisect_left( d[m], i)
    # print("{i:3d}: d[{m}]: {d}  bisect({i}): {bi}".format(m=m, d=d[m], i=i, bi=bisect_left(d[m], i)))

    
    
# for i in range(N-1, -1, -1):

print(ans)
    
    


# Optimized solution
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))

from collections import defaultdict
d = defaultdict(list)


B = [0] * (N+1)
B[0] = 0 
for i in range(0,N):
    B[i+1] = A[i]
    B[i+1] += B[i]

for i in range(0,N+1):
    d[ B[i] % M] += [i]

from bisect import bisect_left

ans = 0
for i in range(0,N+1):
    m = B[i] % M 
    ans += bisect_left( d[m], i)

print(ans)
# Original solution
# coding: utf-8

n,m = list(map(int,input().split()))
a = list(map(int,input().split()))

acc = [0]

for i in range(n):
    acc.append(acc[i]+a[i])    

count = 0
for i in range(n+1):
    for j in range(i):
        if (acc[i]- acc[j]) %m == 0:
            count += 1

print(count)

# Optimized solution
# coding: utf-8
#始点を定めて(n)終点を定めて(n)その間の数を足し合わせる(～n)と計算量オーダーはO(n^3)
#累積和を用いると、始点を定めて(n)終点を定めて(n)差をとればいいので計算量オーダーはO(n^2)
#以下のコードでは、Aのループ処理(n)において随時累積和のmod mを算出し、そのmod mが何回現れたかを示す辞書の検索、挿入を行う(1)ので、計算量オーダーはO(n)
#（辞書の検索計算量オーダーについていまいち理解できていない。本当にO(1)なのだろうか？）

n,m = list(map(int,input().split()))
A = list(map(int,input().split()))

modm = 0
#累積和を別のリストに格納する必要はなく、bという変数を1つ用意して、modmにその時点での累積和のmod mを格納すればよい
dic = {0:1}
#{x:y}:Aの各要素を順に処理していくとき、mod mがxである要素が現時点までにy個見つかっていることを表す

cnt = 0
for a in A:
    modm = (modm+a) %m
    cnt += dic.get(modm,0)
    dic[modm] = dic.get(modm,0) + 1
#c[b]では、bをキーとする要素が見つからなかった場合エラーが発生してしまう。
#c.get(b,default)なら、bをキーとする要素が見つからなかった場合デフォルト値を返してくれる。

print(cnt)
# Original solution
from collections import defaultdict

def main():
    num, person_num = list(map(int, input().split()))
    data = list(map(int, input().split()))

    dp = [defaultdict(int) for i in range(num)]
    dp[0][data[0] % person_num] += 1

    ans = 0
    for i in range(1, num):
        now_data = data[i]
        ans += dp[i - 1][0]
        for key in list(dp[i - 1].keys()):
            now_ind = (key + now_data) % person_num
            dp[i][now_ind] += dp[i - 1][key]
        dp[i][now_data % person_num] += 1

    ans += dp[num - 1][0]

    print(ans)

if __name__ == '__main__':
    main()


# Optimized solution

from collections import defaultdict


def main():
    num_box, num_people = list(map(int, input().split()))
    data = list(map(int, input().split()))

    dp = defaultdict(int)
    dp[0] += 1
    count = 0
    for i in range(num_box):
        count += data[i]
        count %= num_people
        dp[count] += 1

    ans = 0
    for ele in list(dp.values()):
        if ele >= 2:
            ans += (ele - 1) * ele // 2

    print(ans)





if __name__ == '__main__':
    main()
# Original solution
# def f(As, M):
#     prev = None
#     c = 0
#
#     for i, A in enumerate(As):
#         A %= M
#         if i == 0:
#             prev = {A: 1}
#             if A == 0:
#                 c += 1
#             continue
#
#         ccc = {A: 1}
#         for k in prev.keys():
#             v = prev[k]
#             newv = (k + A) % M
#             if newv in ccc:
#                 ccc[newv] += v
#             else:
#                 ccc[newv] = v
#         c += ccc[0] if 0 in ccc else 0
#         prev = ccc
#     return c
def f(As, M):
    totals = [As[0] % M]
    for A in As[1:]:
        totals.append((totals[-1] + A) % M)

    res = 0
    N = len(As)
    for i in range(N):
        ii = totals[N - 1 - i]
        if ii == 0:
            res += 1
        for j in range(i + 1, N):
            jj = totals[N - 1 - j]

            if jj == ii:
                res += 1
    return res


def main():
    N, M = [int(a) for a in input().split()]
    As = [int(a) for a in input().split()]
    print((f(As, M)))


if __name__ == '__main__':
    main()


# Optimized solution
# def f(As, M):
#     prev = None
#     c = 0
#
#     for i, A in enumerate(As):
#         A %= M
#         if i == 0:
#             prev = {A: 1}
#             if A == 0:
#                 c += 1
#             continue
#
#         ccc = {A: 1}
#         for k in prev.keys():
#             v = prev[k]
#             newv = (k + A) % M
#             if newv in ccc:
#                 ccc[newv] += v
#             else:
#                 ccc[newv] = v
#         c += ccc[0] if 0 in ccc else 0
#         prev = ccc
#     return c
def f(As, M):
    totals = [As[0] % M]
    res = 1 if As[0] % M == 0 else 0
    for A in As[1:]:
        l = (totals[-1] + A) % M
        if l == 0:
            res += 1
        totals.append(l)

    # N = len(As)

    ddd = {}
    for t in totals:
        if t not in ddd:
            ddd[t] = 0
        res += ddd[t]
        ddd[t] += 1

    # for i in range(N):
    #     ii = totals[N - 1 - i]
    #     if ii == 0:
    #         res += 1
    #     for j in range(i + 1, N):
    #         jj = totals[N - 1 - j]
    #
    #         if jj == ii:
    #             res += 1
    return res


def main():
    N, M = [int(a) for a in input().split()]
    As = [int(a) for a in input().split()]
    print((f(As, M)))


if __name__ == '__main__':
    main()
# Original solution
import itertools

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

acc = [0] + list(itertools.accumulate(A))

count = 0
for l in range(N + 1):
    for r in range(l + 1, N + 1):
        if (acc[r] - acc[l]) % M == 0:
            count += 1
print(count)

# Optimized solution
import itertools

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

acc = [0] + list(itertools.accumulate(A))

B = [ai % M for ai in acc]
B.sort()
B.append(-1)

result = 0
count = 1

for i in range(N + 1):
    if B[i + 1] == B[i]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
print(result)
# Original solution
n,m = list(map(int,input().split(" ")))
def bar_M(t):
    return int(t)%m
array = list(map(bar_M,input().split(" ")))

array_sum = [0 for i in range(n+1)]
for i in range(1,n+1):
    array_sum[i] = (array_sum[i-1] + array[i-1])%m

nums = set(array_sum)
sums = []
for i in nums:
    p = array_sum.count(i)
    if p > 1:
        sums.append(p)
ans = 0
for i in sums:
    ans+=int((i-1)*i/2)
print(ans)

# Optimized solution
n,m = list(map(int,input().split(" ")))
array = list(map(int,input().split(" ")))

array_sum,sums = [0,0],{0:1}
for i in range(1,n+1):
    array_sum[0] = array_sum[1]
    array_sum[1] = (array_sum[0] + array[i-1])%m
    sums[array_sum[1]] = sums.get(array_sum[1],0) + 1

ans = 0
for i in list(sums.values()):
    ans+=int((i-1)*i/2)
print(ans)
# Original solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
accumA=[]
tmp=0
for i in range(len(A)):
  tmp+=A[i]
  accumA.append(tmp)

accumA=[0]+accumA
cnt=0
for i in range(1,N+1):
  for j in range(i,N+1):
    s=accumA[j]-accumA[i-1]
    if s%M==0:
      cnt+=1

print(cnt)

# Optimized solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
B=[0]
tmp=0
for i in A:
  tmp+=i
  B.append(tmp)

d = {}
for i in B:
  i %= M
  if i not in d:
    d[i] = 0
  d[i] += 1

ans = 0
for i in list(d.values()):
  ans += i*(i-1)//2
print(ans)
# Original solution
from collections import Counter
N, M = list(map(int,input().split()))
A = list(map(int, input().split()))
ans = 0

S = [0 for k in range(N)]
S[0] = A[0]
for k in range(1,N):
    S[k] = S[k-1] + A[k]
S = [0] + S
for k in range(N+1):
    S[k] %= M

C = Counter(S)
for a in C:
    if C[a] >= 2:
        ans += (C[a]*(C[a]-1))//2
print(ans)

# Optimized solution
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N, M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    S = [0]*N
    S[0] = A[0]%M
    for k in range(1,N):
        S[k] = (S[k-1] + A[k])%M
    C = Counter(S)
    C[0] += 1
    ans = 0
    for e in C:
        ans += (C[e]*(C[e]-1))//2
    print(ans)
if __name__ == '__main__':
    main()
# Original solution
from itertools import accumulate
from collections import defaultdict

N,M = list(map(int, input().split()))
A = list(map(int, input().split()))

#1 累積和をとる
B = [0] + list(accumulate(A))

#2 そのmodをとる
B = [b%M for b in B]

#3 1～Nまで、辞書内の当該キーをansにプラスしながら進む
cnt = defaultdict(int)
ans = 0

for b in B:
    ans += cnt[b]
    cnt[b] += 1
    
print(ans)


# Optimized solution
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return list(map(int, stdin.readline().split()))
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return list(map(float, stdin.readline().split()))
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter
from itertools import accumulate

n,m = li()
a = list(li())

acum = list(accumulate(a))
acum = [acumi%m for acumi in acum]

cnt = Counter(acum)

ans = cnt[0]
for k,v in list(cnt.items()):
    ans += v*(v-1)//2
    
print(ans)
# Original solution
from collections import Counter

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
SUM = [0]

for i in a:
    SUM.append((SUM[-1]+i)%m)

#SUM.pop(0)
c = Counter(SUM)
C = c.most_common()
C_srt = sorted(C)
ans = 0

for i in C:
    if i[1] > 1:
        '''
        if i[0] == 0:
            ans += i[1]*(i[1]+1)//2
        else:
        '''
        ans += i[1]*(i[1]-1)//2
    else:
        break
print(ans)


# Optimized solution
from collections import Counter

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
SUM = [0]

for i in a:
    SUM.append((SUM[-1]+i)%m)

c = Counter(SUM)
C = c.most_common()
C_srt = sorted(C)
ans = 0

for i in C:
    if i[1] > 1:
        ans += i[1]*(i[1]-1)//2
    else:
        break
print(ans)
# Original solution
from collections import Counter
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
A.insert(0,0)
cnt = Counter()
for i in range(N): A[i+1] += A[i]
for i in range(N+1): cnt[A[i]%M] += 1
print((sum(n*(n-1)//2 for n in list(cnt.values()))))


# Optimized solution
from collections import Counter
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
A[0] = A[0] % M
for i in range(1,N): A[i] = (A[i]+A[i-1])%M
cnt = Counter([0]+A)
print((sum(n*(n-1)//2 for n in list(cnt.values()))))
# Original solution
from itertools import accumulate as ac
from math import factorial as fc
from collections import Counter

f=lambda a,b:fc(a)//(fc(a-b)*fc(b)) if a>=b>=0 else 0

n,m=list(map(int,input().split()))
*a,=list(map(int,input().split()))
*aa,=[x%m for x in ac([0]+a)]
d=Counter(aa)

v=sum(f(i,2) for i in list(d.values()))
print(v)


# Optimized solution
from collections import Counter

N, M = list(map(int, input().split()))
*A, = list(map(int, input().split()))
ac = [0]*(N+1)

for i in range(1, N+1):
    ac[i] = (ac[i-1]+A[i-1])%M

c = Counter(ac)
ans = 0
for i in list(c.values()):
    ans += i*(i-1)//2
print(ans)
# Original solution
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))

S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2


countlist=dict()
check=set()


for i in range(1,N+1):
    countlist[S[i]]=countlist.get(S[i],0)+1

    
    


ANS=countlist.get(0,0)

for i in list(countlist.keys()):
    ANS+=tr(countlist[i])



print(ANS)






# Optimized solution

N,M=list(map(int,input().split()))
A=list(map(int,input().split()))




S=[0]*(N+1)
for i in range(N):
    S[i+1]=(A[i]+S[i])%M


def tr(k):
    return k*(k-1)//2

S.sort()
S=[-1]+S+[-1]
count=0
ANS=0

for i in range(1,N+3):
    if S[i]==S[i-1]:
        count+=1
    else:
        ANS+=tr(count)
        count=1

print(ANS)
# Original solution
N, M = list(map(int, input().split()))
A = list([x % M for x in list(map(int, input().split()))])
ans = 0
nums = []

for a in A:
    for i in range(len(nums)):
        nums[i] = (nums[i]+a) % M
        if not nums[i]:
            ans += 1
    if not a:
        ans += 1
    nums.append(a)

print(ans)

# Optimized solution
def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    
    b = 0
    count = {0:1}
    ans = 0
    
    for a in A:
        b = (a+b) % M
        if b in count:
            ans += count[b]
            count[b] += 1
        else:
            count[b] = 1
            
    print(ans)

if __name__ == '__main__':
    main()
# Original solution
import math
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
b=[a[0]]
c={}
c[b[0]%m]=1
for i in range(1,n):
  b.append(b[i-1]+a[i])
  c[b[i]%m]=c.get(b[i]%m,0)+1
print((sum([math.factorial(x)//(math.factorial(x-2)*math.factorial(2))if x>1else 0 for x in list(c.values())])+c.get(0,0)))

# Optimized solution
import math
n,m=list(map(int,input().split()))
b=0
c={}
for a in input().split():
  b+=int(a)
  c[b%m]=c.get(b%m,0)+1
print((sum([math.factorial(x)//(math.factorial(x-2)*math.factorial(2))if x>1else 0 for x in list(c.values())])+c.get(0,0)))
# Original solution
import math
n,m=list(map(int,input().split()))
b=0
c={}
for a in input().split():
  b+=int(a)
  c[b%m]=c.get(b%m,0)+1
print((sum([math.factorial(x)//(math.factorial(x-2)*math.factorial(2))if x>1else 0 for x in list(c.values())])+c.get(0,0)))

# Optimized solution
n,m=list(map(int,input().split()));d={0:1};r=s=0
for i in input().split():s+=int(i);s%=m;x=d.get(s,0);r+=x;d[s]=x+1
print(r)
# Original solution
import math
def f(x):return math.factorial(x)
def g(x):return f(x)//(f(x-2)*f(2))if x>1else 0
n,m=list(map(int,input().split()))
b=0
c={}
for a in input().split():
  b+=int(a)
  c[b%m]=c.get(b%m,0)+1
print((sum([g(x) for x in list(c.values())])+c.get(0,0)))

# Optimized solution
n,m,*c=list(map(int,open(0).read().split()))
d={0:1}
r=s=0
for i in c:s+=i;x=d.get(s%m,0);r+=x;d[s%m]=x+1
print(r)
# Original solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
from itertools import accumulate
from collections import Counter
acc = [0]
acc.extend(accumulate(A))
cnt = Counter(ac % M for ac in acc)
print((sum(v * (v - 1) // 2 for v in list(cnt.values()))))

# Optimized solution
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
from itertools import accumulate
from collections import Counter
acc = [0]
acc.extend(accumulate(A))
c = Counter(ac % M for ac in acc)
print((sum(v * (v - 1) // 2 for v in list(c.values()))))
# Original solution
# coding:utf-8

import sys
from collections import Counter


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# Counterを使ったD - Candy Distributionの解法
def solve(N, M, A):
    # 累積和(mod M)を求める
    S = [0]
    for i in range(N):
        S.append((S[-1] + A[i]) % M)
    del S[0]

    # 各要素の個数を数える
    C = Counter(S)

    ans = 0
    for num in C:
        if C[num] <= 1:
            continue
        # C[num]個から2つ選ぶ組み合わせ
        ans += C[num] * (C[num] - 1) // 2

    # 1箱で条件を満たす(Si = 0, l=r)場合を加算
    return ans + C[0]


N, M = inpl()
A = inpl()
print((solve(N, M, A)))


# Optimized solution
# coding:utf-8

import sys
from collections import Counter


input = sys.stdin.readline


def inpl(): return list(map(int, input().split()))


# Counterを使ったD - Candy Distributionの解法
def solve(N, M, A):
    # 累積和S (mod M)を求める
    S = [0]
    for i in range(N):
        S.append((S[-1] + A[i]) % M)

    ans = 0
    # 各要素の個数を数える
    for v in list(Counter(S).values()):
        # v個から2個選ぶ組み合わせ
        ans += v * (v - 1) // 2

    return ans


N, M = inpl()
A = inpl()
print((solve(N, M, A)))
# Original solution
from collections import Counter
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))

ctr = Counter()
ctr[0] = 1

cum = 0
for a in A:
    cum = (cum + a) % M
    ctr[cum] += 1

ans = 0
for v in list(ctr.values()):
    ans += v*(v-1)//2
print(ans)

# Optimized solution
from collections import Counter

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))

cums = [0]
for a in A:
    cums.append((cums[-1] + a) % M)

ctr = Counter(cums)

ans = 0
for v in list(ctr.values()):
    ans += v*(v-1)//2
print(ans)
# Original solution
from collections import defaultdict

from operator import mul
from functools import reduce
 
def cmb(n,r):
    if n < r:
        return 0
    r = min(n-r,r)
    if r == 0:
        return 1
    over = reduce(mul, list(range(n, n - r, -1)))
    under = reduce(mul, list(range(1,r + 1)))
    return over // under

def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    sum_A = [0] * (N+1)

    for i in range(1,N+1):
        sum_A[i] = (sum_A[i-1] + A[i-1]) % M
        
    ans = 0
    d = defaultdict(int)
    for i in range(N+1):
        d[sum_A[i]] += 1

    for i,j in list(d.items()):
        ans += cmb(j,2)

    print(ans)

main()

# Optimized solution
from itertools import accumulate
from collections import defaultdict
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, list(range(n, n - r, -1)))
    under = reduce(mul, list(range(1, r + 1)))
    return over // under

def main():
    N, M = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(accumulate(A))
    d = defaultdict(int)
    for i in range(N):
        B[i] %= M
        d[B[i]] += 1

    cnt = 0
    for i, j in list(d.items()):
        if i == 0:
            cnt += j
        if j >= 2:
            cnt += cmb(j , 2)

    print(cnt)
    
    
            
        
if __name__ == "__main__":
    main()
# Original solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
t = [0]
v = 0
if n > m:
    mod = [0] * m
    for i in range(len(a)):
        v += a[i]
        mod[v%m] += 1
    ans = mod[0]
    for i in range(m):
        ans += mod[i] * (mod[i]-1) / 2
    print((int(ans)))
else:
    ans = 0
    for i in range(len(a)):
        v += a[i]
        t.append(v)
    for i in range(len(t)-1):
        for j in range(i+1, len(t)):
            if (t[j]-t[i]) % m == 0:
                ans += 1
    print(ans)

# Optimized solution
n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
t = [0]
v = 0
b = {0:1}
for i in range(n):
    v = (v + a[i]) % m
    if v in list(b.keys()):
        b[v] += 1
    else:
        b[v] = 1
ans = 0
for i in list(b.values()):
    ans += i * (i-1) / 2
print((int(ans)))
# Original solution
import itertools
from math import factorial
from collections import Counter

ans = 0
N, L = list(map(int, input().split()))
x = list(map(int, input().split()))
y = itertools.accumulate(x)
y = [e % L for e in y]
#print(y)
#print(y)
so = set(y)
#print(so)
#print(so)
counter = Counter([0]+y)
#print(counter.values())
#print
for i in list(counter.values()):
    #print(ans)
    if i>1:ans+=factorial(i) // 2 // factorial(i-2)
print(ans)

# Optimized solution
import itertools
from math import factorial
from collections import Counter

ans = 0
N, L = list(map(int, input().split()))
x = list(map(int, input().split()))
y = itertools.accumulate(x)
y = [e % L for e in y]
#print(y)
#print(y)
so = set(y)
#print(so)
#print(so)
counter = Counter([0]+y)
#print(counter.values())
#print
for i in list(counter.values()):
    #print(ans)
    ans+=i * (i - 1) // 2
print(ans)
# Original solution
N, M = list(map(int, input().split()))
A = [ int(x) for x in input().split() ]

B = [0]
sum_v = 0

for a in A:
    sum_v += a
    sum_v %= M
    B += [ sum_v ]

B.sort()
B += [ "@" ]

cur = B[0]
cnt, ans = 1, 0

for i, b in enumerate(B):
    if B[i+1] == "@":
        ans += cnt*(cnt-1)//2
        break

    if cur == B[i+1]:
        cnt += 1
    else:
        cur = B[i+1]
        ans += cnt*(cnt-1)//2
        cnt = 1

print(ans)


# Optimized solution
N, M = list(map(int, input().split()))
A = [ int(x) for x in input().split() ]

d = {0:1}
ans, s = 0, 0
 
for a in A:
    s += a
    s %= M
    ans += d.get(s, 0)
    d[s] = d.get(s, 0) + 1

print(ans)
# Original solution
import os, sys, re, math

N,M = list(map(int,input().split(' ')))
ary = list(map(int,input().split(' ')))

s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = ary[i] + s[i]

cnt = 0
for j in range(N,0,-1):
    for k in range(j,0,-1):
        if j == k:
            if s[j] % M == 0 and s[j] >= M:
                cnt += 1
        elif (s[j] - s[k]) % M == 0:
            cnt += 1
print(cnt)


# Optimized solution
import os, sys, re, math

N,M = list(map(int,input().split(' ')))
ary = list(map(int,input().split(' ')))

s = [0 for i in range(N+1)]
for i in range(N):
    s[i+1] = (ary[i] + s[i]) % M

m_map = {}

for j in range(0,N+1):
    if s[j] in m_map:
        m_map[s[j]] += 1
    else:
        m_map[s[j]] = 1

ret = 0
for i,v in list(m_map.items()):
    if v >= 2:
        ret += v * (v-1) // 2
print(ret)
# Original solution
N , M = list(map(int,input().split()))
A =  list(map(int,input().split()))
A = [a for a in A]

partial_sum_list = [0]
partial_sum = 0
res = 0
i = 0
while i < N:
    partial_sum += A[i]
    partial_sum_list.append(partial_sum)
    temp = partial_sum % M
    j = 0
    while j < len(partial_sum_list)-1:
        if temp == (partial_sum_list[j] % M):
            res += 1
        j += 1
    i = i + 1
print(res)

# Optimized solution
N , M = list(map(int,input().split()))
A =  list(map(int,input().split()))
A = [a for a in A]

dic = {}
dic[0] = 0
partial_sum = 0
res = 0
i = 0
while i < N:
    partial_sum += A[i]
    a = partial_sum % M
    if a == 0:
        res += 1
    if a in dic:
        dic[a] += 1
        res += dic[a] - 1
    else:
        dic[a] = 1
        res += dic[a] - 1
    #res += dic[a]
    i = i + 1
print(res)
# Original solution
n,m = list(map(int,input().split()))

a = list(map(int,input().split()))

b = [0 for i in range(n+1)]

for i in range(n):
	b[i+1] = b[i]+a[i]


ans = 0
for i in range(n):
	for j in range(1,n-i+1):
		if (b[i+j] - b[i]) % m == 0:
			ans += 1

print(ans)

# Optimized solution
n,m = list(map(int,input().split()))

a = list(map(int,input().split()))

b = [0 for i in range(n+1)]

for i in range(n):
	b[i+1] = (b[i]+a[i])%m

c = {}
for i in b:
	if i in c:
		c[i] += 1
	else:
		c[i] = 1

ans = 0

for i in c:
	ans += (c[i]*(c[i]-1)//2)
print(ans)