Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


dp=[ [] for i in range(N+1) ]
dp[0]=[1]


for i in range(1,N+1):
	W=[]		#WA:累積和
	U=dp[i-1]	#Unit：累積和を計算する前の単位配列
	l=len(U)+A[i-1]	#i行目の配列の長さ

	for j,x in enumerate(U):
		if j==0:	W.append(x)
		else:	W.append(W[-1]+x)

	len_w=len(W)

	L=[]		#dp[i]の配列
	for k in range(l):
		L.append( W[min(k, len_w-1)] )

	for k in range(l-1,-1,-1):
		L[k]=min( L[k] , W[min(l-k-1, len_w-1)] )

	dp[i]=L


try:
	print dp[N][K]%(10**9+7)
except:
	print 0


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0
### BUGGY CODE ###

def run(lst, i):
    lst = [0]+lst+[0]
    cost = 0
    a = lst[:i]+lst[i+1:]
    for a,b in zip(a,a[1:]):
        cost+=abs(b-a)
    return cost

N = int(input())
l = list(map(int,input().split()))
for i in range(1,N+1):
    print(run(l,i))


### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l = [0]+l+[0]
cost = 0
for a,b in zip(l,l[1:]):
    cost += abs(b-a)
for i in range(1,N+1):
    n = cost
    n-=abs(l[i-1]-l[i])
    n-=abs(l[i]-l[i+1])
    n+=abs(l[i-1]-l[i+1])
    print(n)
### BUGGY CODE ###

import sys
imput=sys.stdin.readline
import collections
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=1
if n%2==1 and collections.Counter(a)[0]==1:
    for i in range(2,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
        else:
            ans=(ans%(10**9+7))*2%(10**9+7)
    else:
        print(ans%(10**9+7))
elif n%2==0:
    for i in range(1,n,2):
        if collections.Counter(a)[i]!=2:
            print(0)
            break
        else:
            ans=(ans%(10**9+7))*2%(10**9+7)
    else:
        print(ans%(10**9+7))
else:
    print(0)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
if n%2==1:
    b=[i for i in range(2,n,2)]
    b=b*2
    b.sort()
    #print(a,b)
    b=[0]+b
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
elif n%2==0:
    b=[i for i in range(1,n,2)]
    b=b*2
    b.sort()
    if a==b:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
L = tuple([int(x) for x in sys.stdin.readline().split()])

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        for k in range(j+1, len(L)):
            if L[i] + L[j] <= L[k] or L[j] + L[k] <= L[i] or L[k] + L[i] <= L[j]:
                pass
            else:
                answer += 1

print(answer)


### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = [int(x) for x in sys.stdin.readline().split()]
L.sort()

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        answer += bisect.bisect_left(L, L[i]+L[j])-j-1

print(answer)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

ans = 1
tops = [A[0]]
for i in range(1,N):
    if len(tops) > 1:
        tops.sort(reverse=True)

    for max_i in range(len(tops)):
        if tops[max_i] < A[i]:
            tops[max_i] = A[i]
            break
    else:
        tops.append(A[i])
        ans += 1

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
from collections import deque

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

ans = 1
tops = deque([A[0]])
tops_cnt = 1
for i in range(1,N):
    # print(tops)
    swap_i = bisect.bisect_left(tops,A[i])
    if swap_i:
        # print("hoge",swap_i-1)
        tops[swap_i-1] = A[i]
    # for max_i in range(tops_cnt):
    #     if tops[max_i] < A[i]:
    #         tops[max_i] = A[i]
    #         break
    else:
        tops.appendleft(A[i])
        ans += 1
        tops_cnt += 1

print(ans)
### BUGGY CODE ###

S = list(input())
mod_list = []

for i in range(len(S)-3):
    for j in range(i+4, len(S)+1):
        num = int(''.join(S[i:j]))
        mod_list.append(num % 2019)

print(len([i for i in mod_list if i == 0]))

### FIXED CODE ###

S = list(input())[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1  # If 2019 is exist, count number
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current]
    mods[current] += 1
    x = x * 10 % 2019

print(ans)
### BUGGY CODE ###

N_C = list(map(int, input().split()))
s_t_c = []
for i in range(N_C[0]):
    s_t_c.append(list(map(int, input().split())))

number_list = []
for j in range(10 ** 5):
    number = 0
    for k in range(N_C[0]):
        if s_t_c[k][0] <= j - 1 and s_t_c[k][1] >= j:
            number = number + 1
        if s_t_c[k][0] <= j and s_t_c[k][1] >= j + 1:
            number = number + 1
        if s_t_c[k][0] <= j - 1 and s_t_c[k][1] >= j + 1:
            number = number - 1
    number_list.append(number)

print(max(number_list))

### FIXED CODE ###

n, C = map(int, input().split())
time = 0
stc = []
for i in range(n):
    temp = list(map(int, input().split()))
    time = max(time, temp[1])
    stc.append(temp)
tv = [[0 for i in range(C)] for i in range(time + 1)]
for i in stc:
    s, t, c = i[0], i[1], i[2]
    for j in range(s, t + 1):
        tv[j][c - 1] = 1
ans = 0
for i in tv:
    ans = max(ans, sum(i))
print(ans)
### BUGGY CODE ###

import math
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0

for a in range(N - 2):
    b = a + 1
    c = a + 2
    while c < N and b < N - 1:
        if L[c] >= L[a] + L[b]:
            ans += c - 1 - b
            b += 1
            if b == c:
                c += 1
        else:
            if c == N - 1:
                ans += c - b
                b += 1
            else:
                c += 1
        
print(ans)        

### FIXED CODE ###

import math
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0

for a in range(N - 2):
    b = a + 1
    c = a + 2
    while c < N and b < N - 1:
        if L[c] >= L[a] + L[b]:
            ans += c - 1 - b
            b += 1
            if b == c:
                c += 1
        else:
            if c == N - 1:
                ans += (c - b) * (c - b + 1) // 2 
                break
            else:
                c += 1
        
print(ans)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    import numpy as np
    h, w, n = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    ab_d = {(a, b) for a, b in ab}

    ans = [set() for _ in range(9)]
    for a, b in ab:
        temp = np.full((5, 5), -1, dtype=np.int64)
        for i in range(max(0, 3-a), min(5, h-a+3)):
            for j in range(max(0, 3-b), min(5, w-b+3)):
                if (a+i-2, b+j-2) in ab_d:
                    temp[i, j] = 1
                else:
                    temp[i, j] = 0
        # print(temp)
        yoko_0 = max(3-b, 0)
        yoko_1 = min(w-b+3, 5)
        tate_0 = max(3-a, 0)
        tate_1 = min(h-a+3, 5)
        new_temp = temp[tate_0:tate_1, yoko_0:yoko_1]
        for i in range(tate_1-tate_0-2):
            for j in range(yoko_1-yoko_0-2):
                cnt = np.sum(new_temp[i:i+3, j:j+3])-1
                ans[cnt].add((a+i-2+tate_0, b+j-2+yoko_0))

    for i in range(9):
        ans[i] = len(ans[i])

    print((h-2)*(w-2)-sum(ans))
    for i in ans:
        print(i)


main()


### FIXED CODE ###

h,w,n=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*n]
ab_d={a*(10**9)+b-1 for a,b in ab}

ans=[set() for _ in range(9)]
for a,b in ab:
    temp=[None for _ in [0]*25]
    for i in range(5):
        for j in range(5):
            if 0<a+i-2<=h and 0<b+j-2<=w:
                if (a+i-2)*(10**9)+b+j-3 in ab_d:
                    temp[i*5+j]=1
                else:
                    temp[i*5+j]=0
    for i in range(3):
        for j in range(3):
            cnt=[temp[(i+k)*5+j+l] for k in range(3) for l in range(3)]
            if None not in cnt:
                ans[sum(cnt)-1].add((a+i-2)*(10**9)+b+j-3)
                
for i in range(9):
    ans[i]=len(ans[i])

print((h-2)*(w-2)-sum(ans))
for i in ans:
    print(i)
### BUGGY CODE ###

import numpy as np

N,K = list(map(int, input().split()))
LRs = [list(map(int, input().split())) for _ in range(K)]

dp = np.zeros(N*2+2, dtype = int)
dp[1] = 1

for i in range(1, N+1):
    atai = dp[i]
    for LR in LRs:
        p_array = ([atai] * (LR[1] - LR[0] + 1))
        mae_zero = ([0] * (LR[0] + (i - 1) + 1))
        usiro_zero = ([0] * (N*2 - (i - 1) - LR[1]))
        mae_zero.extend(p_array)
        mae_zero.extend(usiro_zero)
        dp = (dp + np.array(mae_zero)) % 998244353

print(dp[N] % 998244353)

### FIXED CODE ###

import numpy as np

N,K = list(map(int, input().split()))
LRs = [list(map(int, input().split())) for _ in range(K)]

dp = np.zeros(N+2, dtype = int)
dp[1] = 1
dp[2] = -1

atai = 0
for i in range(1, N+2):
    atai += dp[i]
    for LR in LRs:
        if(i+LR[0] <= N):
            dp[i+LR[0]] = (dp[i+LR[0]] + atai) % 998244353
        if(i+LR[1] <= N):
            dp[i+LR[1]+1] = (dp[i+LR[1]+1] -atai) % 998244353

#    print(dp)

#復元
ruisekiwa = [0]

for hoge in dp:
    ruisekiwa.append(ruisekiwa[-1]+hoge)
print(ruisekiwa[N+1] % 998244353)
### BUGGY CODE ###

def main():
  k, q = map(int, input().split())
  d = list(map(int, input().split()))
  from collections import deque
  from itertools import islice
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = deque()
    for i in d:
      i_mod = i % m
      if i_mod == 0:
        d_mod.append(m)
      else:
        d_mod.append(i_mod)
    d_mod_sum = sum(d_mod)
    rep = (n-1) // k
    rem = (n-1) % k
    rem_sum = sum(islice(d_mod, 0, rem))
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import numpy as np
  k, q = map(int, input().split())
  d = np.array(list(map(int, input().split())))
  for i in range(q):
    n, x, m = map(int, input().split())
    x %= m
    d_mod = d % m
    zero_d = k - np.count_nonzero(d_mod)
    d_mod_sum = np.sum(d_mod) + m * zero_d
    rep = (n-1) // k
    rem = (n-1) % k
    zero_rem = len(d_mod[:rem]) - np.count_nonzero(d_mod[:rem])
    rem_sum = np.sum(d_mod[:rem]) + m * zero_rem
    ans = n - 1 - (x + d_mod_sum * rep + rem_sum) // m
    print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
# 下の桁から見ていく
S = S[::-1]
N = len(S)

# dp0[i] := 下からi桁目まで見た時の最小値(直前で繰り上げなし)
dp0 = [INF] * (N+1)
# dp1[i] := 下からi桁目まで見た時の最小値(直前で繰り上げあり)
dp1 = [INF] * (N+1)
dp0[0] = 0
for i, s in enumerate(S):
    s = int(s)
    # この桁で繰り上げない遷移
    dp0[i+1] = min(dp0[i+1], dp0[i] + s)
    dp0[i+1] = min(dp0[i+1], dp1[i] + (s+1))
    # この桁で繰り上げる遷移
    dp1[i+1] = min(dp1[i+1], dp0[i] + 10-s)
    dp1[i+1] = min(dp1[i+1], dp1[i] + 10-(s+1))
# 繰り上げる方は最後の繰り上げ分を足す
ans = min(dp0[N], dp1[N]+1)
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
S = S[::-1]
N = len(S)

dp0 = [INF] * (N+1)
dp1 = [INF] * (N+1)
dp0[0] = 0
for i, s in enumerate(S):
    s = int(s)
    dp0[i+1] = min(dp0[i+1], dp0[i] + s)
    dp1[i+1] = min(dp1[i+1], dp0[i] + 10-s)
    dp0[i+1] = min(dp0[i+1], dp1[i] + (s+1))
    dp1[i+1] = min(dp1[i+1], dp1[i] + 10-(s+1))
ans = min(dp0[N], dp1[N]+1)
print(ans)
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H])
    next_steps = next_steps | set([black-1 for black in blacks if black%W != 0])
    next_steps = next_steps | set([black+1 for black in blacks if black%W != W-1])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()


### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

if __name__ == "__main__":
  main()
### BUGGY CODE ###


a, b, c = map(int, input().split())
 
for i in range(a, b+1):
    if i<a+c or i>b-c:
        print(i)
    else:
        i += b-a-2*c-2

### FIXED CODE ###


a, b, c = map(int, input().split())

if b - a + 1 > 2 * c:
    for i in range(a, a+c):
        print(i)
    for i in range(b-c+1, b+1):
        print(i)
else:
    for i in range(a, b+1):
        print(i)
### BUGGY CODE ###

import copy
N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    answer = 0
    del_A = copy.copy(A)
    del_A.remove(A[i])
    # del_A.sort()
    # print(del_A)
    answer += abs(del_A[0])
    for j in range(1, N-1):
        answer += abs(del_A[j] - del_A[j-1])
    answer += abs(del_A[-1])
    # MIN = min(0, del_A[0])
    # MAX = max(0, del_A[-1])
    # # print(MIN, MAX)
    # answer = abs(MAX - MIN) * 2
    print(answer)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
all = abs(A[0]) + abs(A[N-1])
for i in range(1, N):
    all += abs(A[i] - A[i-1])

for i in range(N):
    answer = all
    if i == 0:
        prev = 0
    else:
        prev = A[i-1]
    if i == N-1:
        next = 0
    else:
        next = A[i+1]
    curr = A[i]
    if prev > curr and curr < next:
        if prev >= next:
            answer -= abs(curr - next) * 2
        else:
            answer -= abs(curr - prev) * 2
    elif prev < curr and curr > next:
        if prev >= next:
            answer -= abs(curr - prev) * 2
        else:
            answer -= abs(curr - next) * 2
    print(answer)
### BUGGY CODE ###

ks= list(map(int, input().split())) 
 
count = 0
 
x = 0
y = 0
z = 0
 
for targetX in range(ks[0]+1):
    
    for targetY in range(ks[0]+1):
        
        z = ks[1] - (targetX + targetY)
        
        if 0 <= z and z <= ks[0]:
            count += 1
            
    
        targetY +=1
        
    targetX +=1
        
 
print(count)

### FIXED CODE ###

ks= list(map(int, input().split())) 
 
count = 0
 
x = 0
y = 0
z = 0
 
for targetX in range(ks[0]+1):
    
    
    if targetX <= ks[0] and ks[1]-(targetX+ks[0]+ks[0]) <= 0:
    
        for targetY in range(ks[0]+1):
            
            z = ks[1] - (targetX + targetY)
            
            if 0 <= z and z <= ks[0]:
                count += 1
                
        
        
        
 
print(count)
### BUGGY CODE ###

while True:
    r,c = map(int, input().split())
    if (r|c)==0: break

    array = []
    for i in range(r):
        array.append(input())
    num = [0]*c
    for i in range(r):
        for j in range(c):
            num[j] = num[j]*2+int(array[i][2*j])

    maxx = -1
    for i in range(1 << r):
        answer = 0
        for j in range(c):
            oksenbei = bin(num[j]^i).count("1")
            answer += max(oksenbei, r-oksenbei)
        maxx = max(maxx, answer)

    print(maxx)

### FIXED CODE ###

while True:
    r,c = map(int, input().split())
    if (r|c)==0: break

    num = [0]*c
    for i in range(r):
        instr = input()
        for j in range(c):
            num[j] = (num[j]<<1) + (instr[2*j]=="1")

    maxx = -1
    for i in range(1 << r):
        answer = 0
        for j in range(c):
            oksenbei = bin(num[j]^i).count("1")
            answer += oksenbei if oksenbei*2//r >= 1 else r-oksenbei
        if maxx < answer:
            maxx = answer

    print(maxx)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

min_b = min(B)
max_b = max(B)
max_c = max(C)
summs = []
for a in A:
    for b in B:
        if len(summs) >= K and a + b + max_c < summs[K-1]:
            break

        for c in C:
            summ = a + b + c
            if len(summs) >= K:
                min_sum = summs[K-1]    
                if summ < min_sum:
                    break
            summs.append(summ)
        summs.sort(reverse=True)

for s in summs[0:K]:
    print(s)

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N , M = map(int, input().split())
an = list(map(int,input().split()))
ca = [0] * N
ca[0] = an[0] % M
ans = 0
for i in range(1,N):
    ca[i] = (ca[i-1] + an[i]) % M
for i in range(N):
    if ca[i] % M == 0:
        ans += 1
    for j in range(i):
        if (ca[i] - ca[j]) % M == 0:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
from math import factorial
# Mで割った余りが同じ累積和同士の組み合わせを数え上げればよい
N , M = map(int, input().split())
an = list(map(int,input().split()))
ca = [0] * N
ca[0] = an[0] % M
ans = 0
for i in range(N):
    if i > 0:
        ca[i] = (ca[i-1] + an[i]) % M
    if ca[i] % M == 0:
        ans += 1
# Mで割った余りが同じ個数をCounterを利用して求める
c = list(Counter(ca).items())
for ci in c:
    if ci[1] >= 2:
        ans += factorial(ci[1]) // (factorial(2) * factorial(ci[1]-2))
print(ans)
### BUGGY CODE ###

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+9)

    zero =  A.count(1)
    if zero>1:
        print(0)
        return
    if zero==1:
        print(1)
        return

    for i in range(lenb):
        for j in range(i+1,lenb):
            if Boo[j] and s[B[j]-1]==False and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and A.count(B[i])==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

a,b=map(int,input().split())
tem=max(a,b)
while 1:
    if tem%a==0  and tem%b==0:
        print(tem)
        break
    else:
        tem+=1

### FIXED CODE ###

import math as mt
a,b=map(int,input().split())
tem=max(a,b)
c=1
if a==b:
    print(a)
elif min(a,b)==1:
    print(max(a,b))
elif a%b==0 or b%a==0:
    print(max(a,b))
else:
        
    while 1:
        c+=1
        if (tem*c)%a==0 and (tem*c)%b==0:
            print(tem*c)
            break
### BUGGY CODE ###

H, W = map(int, input().split())
A = []
B = []
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[[] for _ in range(W)] for _ in range(H)]
dp[0][0].append(d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] += list(map(lambda x: x+d[h+1][w], dp[h][w]))
            dp[h+1][w] += list(map(lambda x: abs(x-d[h+1][w]), dp[h][w]))
        if w < W-1:
            dp[h][w+1] += list(map(lambda x: x+d[h][w+1], dp[h][w]))
            dp[h][w+1] += list(map(lambda x: abs(x-d[h][w+1]), dp[h][w]))
print(min(dp[-1][-1]))

### FIXED CODE ###

def max2(x,y):
    return x if x > y else y

H, W = map(int, input().split())
A = []
B = []
ofs = 80*H*W
for _ in range(H):
    A.append(list(map(int, input().split())))
for _ in range(H):
    B.append(list(map(int, input().split())))
d = [[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        d[h][w] = abs(A[h][w]-B[h][w])

dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1<<ofs
dp[0][0] = (dp[0][0]<<d[0][0])|(dp[0][0]>>d[0][0])
for h in range(H):
    for w in range(W):
        if h < H-1:
            dp[h+1][w] |= (dp[h][w]<<d[h+1][w])|(dp[h][w]>>d[h+1][w])
        if w < W-1:
            dp[h][w+1] |= (dp[h][w]<<d[h][w+1])|(dp[h][w]>>d[h][w+1])
res = dp[-1][-1]>>ofs
print((-res&res).bit_length()-1)