Buggy python submission (verdict: Time Limit Exceeded):
class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] // self.fact[r] // self.fact[n - r]


from collections import defaultdict

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

accA = [0] * (N + 1)
for i, a in enumerate(A, start=1):
    accA[i] = accA[i - 1] + a

cnt = defaultdict(int)
for a in accA:
    cnt[a % M] += 1

comb = Combination(N + 100)
ans = 0
for c in cnt.values():
    ans += comb.ncr(c, 2)

print(ans)

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

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

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

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

dp = [defaultdict(int) for _ in range(N + 1)]

for i, a in enumerate(A, start=1):
    dp[i][a] += 1
    for s, cnt in dp[i - 1].items():
        dp[i][(s + a) % M] += cnt

ans = 0
for cnt in dp[1:]:
    ans += cnt[0]

print(ans)

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

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

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

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

dp = [defaultdict(int) for _ in range(N + 1)]

for i, a in enumerate(A, start=1):
    dp[i][a] += 1
    for s, cnt in dp[i - 1].items():
        dp[i][(s + a) % M] += cnt

ans = 0
for cnt in dp[1:]:
    ans += cnt[0]

print(ans)

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

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

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))

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

ans = 0
for l in range(1, N+1) :
    for r in range(l, N+1) :
        tas = S[r] - S[l-1]
        if tas % M == 0 :
            ans += 1

print(ans)



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

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

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

print(ans)