Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[0]*N
def f(x):
    if len(table[x])==0:
        return
    for i in table[x]:
        if dp[i]<dp[x]+1:
            dp[i]=dp[x]+1
            f(i)
    return
for i in H:
    f(i)
print(max(dp))

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[-1]*N
def f(x):
    if dp[x]!=-1:
        return dp[x]
    if len(table[x])==0:
        return 0
    t=0
    for i in table[x]:
        t=max(t,f(i)+1)
    dp[x]=t
    return t
for i in H:
    f(i)
print(max(dp))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[0]*N
def f(x):
    if len(table[x])==0:
        return
    for i in table[x]:
        dp[i]=max(dp[x]+1,dp[i])
        f(i)
    return
for i in H:
    f(i)
print(max(dp))

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
table=[[] for i in range(N)]
Lin=[0]*N
for i in range(M):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    Lin[v-1]+=1
H=[]
for i in range(N):
    if Lin[i]==0:
        H.append(i)
dp=[-1]*N
def f(x):
    if dp[x]!=-1:
        return dp[x]
    if len(table[x])==0:
        return 0
    t=0
    for i in table[x]:
        t=max(t,f(i)+1)
    dp[x]=t
    return t
for i in H:
    f(i)
print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])

Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
dp=[-1]*(K+1)#0=False 1=True
def sea(i):
    if dp[i]!=-1:
        return dp[i]
    s=1
    flag=0
    for a in A:
        if i-a>=0:
            flag=1
            s*=sea(i-a)
    if flag==0:
        dp[i]=0
        return 0
    dp[i]=1-s
    return 1-s
if sea(K)==0:
    print('Second')
else:
    print('First')

Fixed submission:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
dp=[0]*(K+1)
dp[0]=0
for i in range(1,K+1):
    flag=0
    s=1
    for a in A:
        if i-a>=0:
            s*=dp[i-a]
            flag=1
    if flag==0:
        dp[i]=0
    else:
        dp[i]=1-s
#print(dp)
if dp[K]==0:
    print('Second')
else:
    print('First')
Buggy python submission (verdict: Runtime Error):
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    table[v-1].append(w-1)
mod=10**9+7
f=[-1]*N
g=[-1]*N
def ser(par,son):
    if f[son]!=-1 and g[son]!=-1:
        return f[son],g[son]
    s=1
    t=1
    for grason in table[son]:
        if grason==par:
            continue
        x,y=ser(son,grason)
        s*=x
        s%=mod
        t*=(x+y)
        t%=mod
    f[son],g[son]=t,s
    return t,s
z=1
w=1
for i in table[0]:
    ser(0,i)
    z*=f[i]
    z%=mod
    w*=(f[i]+g[i])
    w%=mod
print((z+w)%mod)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    table[v-1].append(w-1)
mod=10**9+7
f=[-1]*N
g=[-1]*N
def ser(par,son):
    if f[son]!=-1 and g[son]!=-1:
        return f[son],g[son]
    s=1
    t=1
    for grason in table[son]:
        if grason==par:
            continue
        x,y=ser(son,grason)
        s*=x
        s%=mod
        t*=(x+y)
        t%=mod
    f[son],g[son]=t,s
    return t,s
z=1
w=1
for i in table[0]:
    ser(0,i)
    z*=f[i]
    z%=mod
    w*=(f[i]+g[i])
    w%=mod
print((z+w)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

stdin = sys.stdin

sys.setrecursionlimit(10 ** 5)


def li(): return map(int, stdin.readline().split())


def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())


def lf(): return 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())


l, n = li()
x = [ni() for _ in range(n)]

#dp = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
dp0 = [[0]*(n+1) for _ in range(n + 1)]
dp1 = [[0]*(n+1) for _ in range(n + 1)]
left = [0] + x
right = [l] + x[::-1]

for total in range(1, n + 1):
    for ccw in range(total + 1):
        cw = total - ccw
        if ccw == 0:
            dp1[ccw][cw] = dp1[ccw][cw - 1] + (right[cw - 1] - right[cw])

        elif cw == 0:
            dp0[ccw][cw] = dp0[ccw - 1][cw] + (left[ccw] - left[ccw - 1])

        else:
            dp0[ccw][cw] = max(dp1[ccw - 1][cw] + (left[ccw] + l - right[cw]),
                                 dp0[ccw - 1][cw] + (left[ccw] - left[ccw - 1]))

            dp1[ccw][cw] = max(dp1[ccw][cw - 1] + (right[cw - 1] - right[cw]),
                                 dp0[ccw][cw - 1] + (left[ccw] + l - right[cw]))
ans = 0
for ccw in range(n + 1):
    cw = n - ccw
    ans = max(ans, dp0[ccw][cw], dp1[ccw][cw])

print(ans)


Fixed submission:
L, N = map(int, input().split())
X = [int(input()) for i in range(N)]
Y = [L - X[-i] for i in range(1, N + 1)]


def check(T, N):
    X = [0] + T
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = P[i - 1] + X[i]
    for i in range(N, 0, -1):
        Q[i - 1] = Q[i] + L - X[i]
    ans = -1
    for i in range(1, N + 1):
        k = N - i
        if k % 2 == 0:
            a = k // 2
            t = 2 * (P[i + a - 1] - P[i - 1]) + 2 * (Q[i + a]) + X[i + a]
        else:
            a = k // 2
            t = 2 * (P[i + a] - P[i - 1]) + 2 * (Q[i + a + 1]) + L - X[i + a + 1]
        ans = max(ans, t)
        # print(t)
    return ans


print(max(check(X, N), check(Y, N)))
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil,log
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    dp=[[0]*16 for i in range(N)]
    for i in range(16):
        dp[N-1][i]=i
    for n in range(N-2,-1,-1):
        nx=ceil(log(A[n]/A[n+1])/log(4)) #A
        for x in range(16):
            dx=nx+x
            if dx <=15:
                #print(max(0,dx))
                dp[n][x]=dp[n+1][max(0,dx)]+x
            else:
                dp[n][x]=dp[n+1][15]+x+(N-1-n)*(dx-15)
    L=[0]*N
    for i in range(N):
        L[i]=dp[i][0]
    return L

K=f(A)+[0]
L=[0]+f(A[::-1])[::-1]
ans=10**9
for i in range(N):
    ans=min(ans,i+2*L[i]+2*K[i])
print(ans)

Fixed submission:
from math import ceil,log
N=int(input())
A=[int(i) for i in input().split()]
def f(A):
    dp=[0]*16
    L=[0]*N
    for i in range(16):
        dp[i]=i
    for n in range(N-2,-1,-1):
        ndp=[0]*16
        nx=ceil(log(A[n]/A[n+1])/log(4)) #A
        for x in range(16):
            dx=nx+x
            if dx <=15:
                #print(max(0,dx))
                ndp[x]=dp[max(0,dx)]+x
            else:
                ndp[x]=dp[15]+x+(N-1-n)*(dx-15)
        dp=ndp
        L[n]=dp[0]
    return L

K=f(A)+[0]
L=[0]+f(A[::-1])[::-1]
ans=10**22
for i in range(N+1):
    ans=min(ans,i+2*L[i]+2*K[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
def debug(*args): print(*args, file=sys.stderr)
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#print(dd)
B=sorted(A,reverse=True)
ans=0
for x in B:
    debug(*args)
    #print(x)
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            #print(ans)
            #print(dd)
    else:
        s+=1
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)




Fixed submission:
from collections import defaultdict
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
for a in A:
    dd[a]+=1
#print(dd)
B=sorted(A,reverse=True)
ans=0
for x in B:
    #print(x)
    if dd.get(x,-1)==0:
        continue
    s=len(bin(x))-3
    if x==1<<s:
        t=dd.get(x,-1)
        if t!=-1:
            ans+=t//2
            dd[x]-=(t//2)*2
            #print(ans)
            #print(dd)
    else:
        s+=1
        #print((1<<s)-x)
        t=dd.get((1<<s)-x,-1)
        if t>=1:
            ans+=1
            dd[x]-=1
            dd[(1<<s)-x]-=1
            #print(ans)
            #print(dd)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
def f(K):
    L=deque()
    L.append([0,A[0]])
    for i in range(N-1):
        #print(L)
        if A[i]<A[i+1]:
            L.append([0,A[i+1]-A[i]])
            continue
        t=A[i]-A[i+1]
        while t-L[-1][1]>=0:
            t-=L[-1][1]
            L.pop()
            #print(L)
        L[-1][1]-=t
        #if L[-1][1]==0:
            #L.pop()
        if L[-1][0]!=K-1:
            if L[-1][1]==1:
                L[-1][0]+=1
            else:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
        else:
            s=0
            while len(L)!=0 and L[-1][0]==K-1:
                s+=L[-1][1]
                L.pop()
            if len(L)==0:
                return False
            elif L[-1][1]==1:
                L[-1][0]+=1
                L.append([0,s])
            elif L[-1][1]!=1:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
                L.append([0,s])
    #print(L)
    return True



mi=0
ma=2*10**5+1
while ma-mi>1:
    mid=(ma+mi)//2
    if f(mid):
        ma=mid
    else:
        mi=mid
print(ma)


Fixed submission:
from collections import deque
N=int(input())
A=[int(i) for i in input().split()]
def f(K):
    L=deque()
    L.append([0,A[0]])
    for i in range(N-1):
        #print(L)
        if A[i]<A[i+1]:
            L.append([0,A[i+1]-A[i]])
            continue
        t=A[i]-A[i+1]
        while t-L[-1][1]>=0:
            t-=L[-1][1]
            L.pop()
            #print(L)
        L[-1][1]-=t
        #if L[-1][1]==0:
            #L.pop()
        if L[-1][0]!=K-1:
            if L[-1][1]==1:
                L[-1][0]+=1
            else:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
        else:
            s=0
            while len(L)!=0 and L[-1][0]==K-1:
                s+=L[-1][1]
                L.pop()
            if len(L)==0:
                return False
            elif L[-1][1]==1:
                L[-1][0]+=1
                L.append([0,s])
            elif L[-1][1]!=1:
                L[-1][1]-=1
                L.append([L[-1][0]+1,1])
                L.append([0,s])
    #print(L)
    return True



mi=0
ma=2*10**5+1
while ma-mi>1:
    mid=(ma+mi)//2
    if f(mid):
        ma=mid
    else:
        mi=mid
print(ma)
Buggy python submission (verdict: Runtime Error):
N=int(input())
S=input()
Q=int(input())
K=[int(i) for i in input().split()
def f(k):
    num=0
    L=[0,0,0]
    for i in range(N):
        if i-k>=0:
            if S[i-k]=='D':
                L[0]-=1
                L[2]-=L[1]
            elif S[i-k]=='M':
                L[1]-=1
        if S[i]=='D':
            L[0]+=1
        elif S[i]=='M':
            L[1]+=1
            L[2]+=L[0]
        elif S[i]=='C':
            num+=L[2]
        #print(i,':',L,':',num)
    return num
for k in K:
    print(f(k))

Fixed submission:
N=int(input())
S=input()
Q=int(input())
K=[int(i) for i in input().split()]
def f(k):
    num=0
    L=[0,0,0]
    for i in range(N):
        if i-k>=0:
            if S[i-k]=='D':
                L[0]-=1
                L[2]-=L[1]
            elif S[i-k]=='M':
                L[1]-=1
        if S[i]=='D':
            L[0]+=1
        elif S[i]=='M':
            L[1]+=1
            L[2]+=L[0]
        elif S[i]=='C':
            num+=L[2]
        #print(i,':',L,':',num)
    return num
for k in K:
    print(f(k))
Buggy python submission (verdict: Runtime Error):
K,N=map(int,input().split())
mod=998244353
table=[1]*(2*N+5)
t=1
for i in range(1,2*N+5):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(2*N+5)
t=1
for i in range(1,2*N+5):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
ans=[]
for k in range(2,K+2):
    num=0
    if k%2==1:
        l=k//2
        p=l
        r=K-2*l
        for q in range(l+1):
            if N-q>=0 and r+q-1>=0:
                s=(table[l]*rtable[q]*rtable[l-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num=num%mod
                #print(10,q,k,l,p,num,s)
        ans.append(num)
    else:
        l=k//2
        p=l-1
        r=K-k+1
        for q in range(p+1):
            if N-q-1>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-2]*rtable[N-q-1]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod
                #print(9,q,k,l,p,num,s)
            if N-q>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod 
                #print(10,q,k,l,p,num,s)
        ans.append(num)
print('\n'.join(map(str,ans)))
ans=ans[::-1]
print('\n'.join(map(str,ans[1:])))

Fixed submission:
K,N=map(int,input().split())
mod=998244353
L=max(K,N)
table=[1]*(3*L+5)
t=1
for i in range(1,3*L+5):
    t*=i
    t%=mod
    table[i]=t
rtable=[1]*(3*L+5)
t=1
for i in range(1,3*L+5):
    t*=pow(i,mod-2,mod)
    t%=mod
    rtable[i]=t
ans=[]
for k in range(2,K+2):
    num=0
    if k%2==1:
        l=k//2
        p=l
        r=K-2*l
        for q in range(l+1):
            if N-q>=0 and r+q-1>=0:
                s=(table[l]*rtable[q]*rtable[l-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num=num%mod
                #print(10,q,k,l,p,num,s)
        ans.append(num)
    else:
        l=k//2
        p=l-1
        r=K-k+1
        for q in range(p+1):
            if N-q-1>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-2]*rtable[N-q-1]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod
                #print(9,q,k,l,p,num,s)
            if N-q>=0 and r+q-1>=0:
                s=(table[p]*rtable[q]*rtable[p-q])%mod
                s=(s*pow(2,q,mod))%mod
                t=(table[N+r-1]*rtable[N-q]*rtable[r+q-1])%mod
                s=(s*t)%mod
                num+=s
                num%=mod 
                #print(10,q,k,l,p,num,s)
        ans.append(num)
print('\n'.join(map(str,ans)))
ans=ans[::-1]
print('\n'.join(map(str,ans[1:])))
Buggy python submission (verdict: Time Limit Exceeded):
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    ma=0
    mi=0
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
        ma=max(p[i],ma)
        mi=min(p[i],mi)
    tree=BIT(ma-mi+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]-mi+1)
        tree.add(p[i-1]-mi+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)


Fixed submission:
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
    tree=BIT(2*N+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]+N+1)
        tree.add(p[i-1]+N+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9+1
y=-1
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)
Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
N, M = list(map(int, input().split()))
P=map(int, input().split())
Acnt = [0 for i in range(M)]
sym = 0

for A in P:
    sym = (sym + A) % M
    Acnt[sym] += 1
L=[cnt * (cnt - 1) for cnt in Acnt]
print(int(Acnt[0] + sum(L) / 2))



Fixed submission:
from collections import defaultdict
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
dd=defaultdict(int)
for p in P:
    dd[p%M]+=1
ans=0
def dou(x):
    return (x*(x-1))//2
for s in dd.values():
    ans+=dou(s)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# encoding: utf-8
N, M = list(map(int, input().split()))
P=map(int, input().split())
Acnt = [0 for i in range(M)]
sym = 0

for A in P:
    sym = (sym + A) % M
    Acnt[sym] += 1

print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))



Fixed submission:
from collections import defaultdict
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
dd=defaultdict(int)
for p in P:
    dd[p%M]+=1
ans=0
def dou(x):
    return (x*(x-1))//2
for s in dd.values():
    ans+=dou(s)
print(ans)

Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
P=map(int, input().split()):
Acnt = [0 for i in range(M)]
sym = 0

for A in P:
    sym = (sym + A) % M
    Acnt[sym] += 1

print(int(Acnt[0] + sum([cnt * (cnt - 1) for cnt in Acnt]) / 2))



Fixed submission:
from collections import defaultdict
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
dd=defaultdict(int)
for p in P:
    dd[p%M]+=1
ans=0
def dou(x):
    return (x*(x-1))//2
for s in dd.values():
    ans+=dou(s)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
# input = sys.stdin.readline
S = list(input())
p = 10 ** 9 + 7
# p = 10 ** 18

A = AB = ABC = 0
Q = 0
for i, Si in enumerate(S):
    # print("#", A, AB, ABC)
    if Si == 'A':
        A = (A + 1 * (3 ** Q)) % p
    elif Si == 'B':
        AB = (AB + A) % p
    elif Si == 'C':
        ABC = (ABC + AB) % p
    else:
        ABC = (3 * ABC + AB) % p
        AB = (3 * AB + A) % p
        #A = (3 * A + 1 * (3 ** Q)) % p
        A = (3 * A + 1 * (pow(3,Q,p))) % p
        Q += 1

print(ABC)


Fixed submission:
S=input()
N=len(S)
mod=pow(10,9)+7
dpa=[0]*N
dpl=[0]*N
dpc=[0]*N
dpr=[0]*N
for i in range(1,N):
    if S[i-1]=='A':
        dpa[i]=dpa[i-1]+1
        dpl[i]=dpl[i-1]
    elif S[i-1]=='?':
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]+1
    else:
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]
for i in range(N-2,-1,-1):
    if S[i+1]=='C': 
        dpc[i]=dpc[i+1]+1
        dpr[i]=dpr[i+1]
    elif S[i+1]=='?': 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]+1
    else: 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]
ans=0 
for i in range(1,N-1):
    if S[i]=='?' or S[i]=='B':
        x=pow(3,dpl[i],mod)
        y=pow(3,max(dpl[i]-1,0),mod)
        z=pow(3,dpr[i],mod)
        w=pow(3,max(dpr[i]-1,0),mod)
        x=(x*dpa[i])%mod
        y=(y*dpl[i])%mod
        z=(z*dpc[i])%mod
        w=(w*dpr[i])%mod
        s=(x+y)%mod
        u=(z+w)%mod
        t=(s*u)%mod
        ans = (ans+t)%mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
# input = sys.stdin.readline
S = list(input())
p = 10 ** 9 + 7
# p = 10 ** 18

A = AB = ABC = 0
Q = 0
for i, Si in enumerate(S):
    # print("#", A, AB, ABC)
    if Si == 'A':
        A = (A + 1 * (3 ** Q)) % p
    elif Si == 'B':
        AB = (AB + A) % p
    elif Si == 'C':
        ABC = (ABC + AB) % p
    else:
        ABC = (3 * ABC + AB) % p
        AB = (3 * AB + A) % p
        #A = (3 * A + 1 * (3 ** Q)) % p
        A = (3 * A + 1 * (pow(3,Q))) % p
        Q += 1

print(ABC)


Fixed submission:
S=input()
N=len(S)
mod=pow(10,9)+7
dpa=[0]*N
dpl=[0]*N
dpc=[0]*N
dpr=[0]*N
for i in range(1,N):
    if S[i-1]=='A':
        dpa[i]=dpa[i-1]+1
        dpl[i]=dpl[i-1]
    elif S[i-1]=='?':
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]+1
    else:
        dpa[i]=dpa[i-1]
        dpl[i]=dpl[i-1]
for i in range(N-2,-1,-1):
    if S[i+1]=='C': 
        dpc[i]=dpc[i+1]+1
        dpr[i]=dpr[i+1]
    elif S[i+1]=='?': 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]+1
    else: 
        dpc[i]=dpc[i+1]
        dpr[i]=dpr[i+1]
ans=0 
for i in range(1,N-1):
    if S[i]=='?' or S[i]=='B':
        x=pow(3,dpl[i],mod)
        y=pow(3,max(dpl[i]-1,0),mod)
        z=pow(3,dpr[i],mod)
        w=pow(3,max(dpr[i]-1,0),mod)
        x=(x*dpa[i])%mod
        y=(y*dpl[i])%mod
        z=(z*dpc[i])%mod
        w=(w*dpr[i])%mod
        s=(x+y)%mod
        u=(z+w)%mod
        t=(s*u)%mod
        ans = (ans+t)%mod
print(ans)