CodeEff/ECCO huggingface dataset:
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

INF = 10**18

N = int(readline())
ABC = [list(map(int, readline().split())) for _ in range(N - 1)]
Q, K = list(map(int, readline().split()))
XY = [list(map(int, readline().split())) for _ in range(Q)]


def warshall_floyd(dist):
    for k, _ in enumerate(dist):
        for i, _ in enumerate(dist):
            for j, _ in enumerate(dist):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


dist = [[INF] * (N + 1) for _ in range(N + 1)]
for abc in ABC:
    dist[abc[0] - 1][abc[1] - 1] = abc[2]
    dist[abc[1] - 1][abc[0] - 1] = abc[2]

dist = warshall_floyd(dist)

for x, y in XY:
    print((dist[x - 1][K - 1] + dist[K - 1][y - 1]))


# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = list(map(int, readline().split()))
    edges[a].append((b, c))
    edges[b].append((a, c))

Q, K = list(map(int, readline().split()))

dist = [0] * (N + 1)


def dfs(v, p, d):
    dist[v] = d

    for n, dd in edges[v]:
        if n == p:
            continue
        dfs(n, v, d + dd)


dfs(K, -1, 0)

for _ in range(Q):
    x, y = list(map(int, readline().split()))
    print((dist[x] + dist[y]))
# Original solution
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = list(map(int, readline().rstrip().split()))
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = list(map(int, readline().rstrip().split()))
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    for n, c in path[K]:
        dist[n] = c
        
    que = deque([(K, n) for n, c in path[K]])
    while que:
        pre, now = que.popleft()
        for next, d in path[now]:
            if next != pre:
                dist[next] = dist[now] + d
                que.append((now, next))

    for _ in range(Q):
        x, y = list(map(int, readline().rstrip().split()))
        print((dist[x-1] + dist[y-1]))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = list(map(int, readline().rstrip().split()))
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = list(map(int, readline().rstrip().split()))
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    
    que = deque([K])
    while que:
        pre = que.popleft()
        for next, d in path[pre]:
            if dist[next] == -1:
                dist[next] = dist[pre] + d
                que.append(next)

    for _ in range(Q):
        x, y = list(map(int, readline().rstrip().split()))
        print((dist[x-1] + dist[y-1]))

if __name__ == '__main__':
    main()
# Original solution
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N = int(readline())
    path = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = list(map(int, readline().rstrip().split()))
        path[a-1].append((b-1, c))
        path[b-1].append((a-1, c))
    Q, K = list(map(int, readline().rstrip().split()))
    K -= 1

    dist = [-1] * N
    dist[K] = 0
    
    que = deque([K])
    while que:
        pre = que.popleft()
        for next, d in path[pre]:
            if dist[next] == -1:
                dist[next] = dist[pre] + d
                que.append(next)

    for _ in range(Q):
        x, y = list(map(int, readline().rstrip().split()))
        print((dist[x-1] + dist[y-1]))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop


def dijkstra(path, N, start):
    """
    Args:
        path (list): [[(cost, node), (cost, node), ...], [], [], ...]
    """
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))

    return dist


def main():
    N = int(readline())
    path = [[] for _ in range(N)]

    for _ in range(N-1):
        a, b, c = list(map(int, readline().rstrip().split()))
        path[a-1].append((c, b-1))
        path[b-1].append((c, a-1))
    
    Q, K = list(map(int, readline().rstrip().split()))
    dist = dijkstra(path, N, K-1)

    for _ in range(Q):
        x, y = list(map(int, readline().rstrip().split()))
        print((dist[x-1] + dist[y-1]))


if __name__ == '__main__':
    main()
# Original solution
# ABC070 D - Transit Tree Path
import heapq
def dijkstra_heap(s):
    """
    始点sから各頂点への最短距離を返す

    Parameters
    ----------
    s : int
        視点とする頂点

    Returns
    -------
    d ：list
    始点sから各頂点への最短距離
    """
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #未使用の頂点の中から最小の距離のものを探す
        if not used[minedge[0]]:
            continue
        v = minedge[0]
        d[v] = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[0]]:
                heapq.heappush(edgelist,[e[0],e[1]+d[v]])
    return d

n=int(eval(input()))
edge=[[] for i in range(n)]
for i in range(n-1):
    a,b,c=list(map(int,input().split()))
    a-=1
    b-=1
    edge[a].append([b,c])
    edge[b].append([a,c])

q,k=list(map(int,input().split()))
k-=1
dist=dijkstra_heap(k)
for i in range(q):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    print((dist[x]+dist[y]))

# Optimized solution
import sys
sys.setrecursionlimit(100000000)
def dfs(cur,par,d):
    dist[cur]=d
    for nx,nx_dist in G[cur]:
        if nx==par:continue
        dfs(nx,cur,d+nx_dist)

n=int(eval(input()))
G=[[] for i in range(n)]
dist=[0]*n
for i in range(n-1):
    a,b,c=list(map(int,input().split()))
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])
q,k=list(map(int,input().split()))
k-=1
dfs(k,-1,0)
for i in range(q):
    x,y=list(map(int,input().split()))
    x-=1
    y-=1
    print((dist[x]+dist[y]))
# Original solution
n=int(eval(input()))
G=[[] for i in range(n)]
for i in range(n-1):
  u,v,w=list(map(int,input().split()))
  G[u-1].append([v-1,w])
  G[v-1].append([u-1,w])
dist=[-1]*n
from collections import deque
Q,k=list(map(int,input().split()))
q=deque()
q.append(k-1)
dist[k-1]=0
while q:
  cur=q.popleft()
  for nx,nd in G[cur]:
    if dist[nx]!=-1:continue
    dist[nx]=dist[cur]+nd
    q.append(nx)
for i in range(Q):
  x,y=list(map(int,input().split()))
  x-=1
  y-=1
  print((dist[x]+dist[y]))


# Optimized solution
from heapq import heappop,heappush
def dijkstra(s,n,edge):
  """
  始点sから各頂点への最短距離を返す

  Parameters
  ----------
  s : int
      視点とする頂点（0-indexed）
  n : int
      グラフの要素数
  eage:list
      グラグ

  Returns
  -------
  dist ：list
  始点sから各頂点への最短距離
  """
  dist=[float("inf")]*n
  dist[s]=0
  used=[-1]*n
  hq=[[dist[s],s]]
  while hq:
    d,cur=heappop(hq)
    if dist[cur]<d:continue # 距離が最小でない場合は飛ばす
    for nx,nxd in edge[cur]:
      if dist[cur]+nxd<dist[nx]:
        dist[nx]=dist[cur]+nxd
        used[nx]=cur
        heappush(hq,[dist[cur]+nxd,nx])
  return dist

n=int(eval(input()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
  a,b,c=list(map(int,input().split()))
  a-=1
  b-=1
  edge[a].append((b,c))
  edge[b].append((a,c))


q,k=list(map(int,input().split()))
xy=[list(map(int,input().split()))for _ in range(q)]
d=dijkstra(k-1,n,edge)
for x,y in xy:
  print((d[x-1]+d[y-1]))
# Original solution
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(eval(input()))
for i in range(n - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    tree[a].append((b, c))
    tree[b].append((a, c))

q, k = list(map(int, input().split()))
k -= 1

dfs(k, -1, 0)
for i in range(q):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    print((depth[x] + depth[y]))


# Optimized solution
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

def input():
    return sys.stdin.readline()[:-1]


def dfs(v, parent, d):
    depth[v] = d
    for to, cost in tree[v]:
        if to == parent:
            continue
        dfs(to, v, d + cost)


depth = defaultdict(int)
tree = defaultdict(list)
n = int(eval(input()))
for i in range(n - 1):
    a, b, c = list(map(int, input().split()))
    a -= 1
    b -= 1
    tree[a].append((b, c))
    tree[b].append((a, c))

q, k = list(map(int, input().split()))
k -= 1

dfs(k, -1, 0)
for i in range(q):
    x, y = list(map(int, input().split()))
    x -= 1
    y -= 1
    print((depth[x] + depth[y]))
# Original solution
N = int(eval(input()))
d = [0] * N
INF = float('inf')

cost = [[INF] * N for i in range(N)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    cost[a - 1][b- 1] = c
    cost[b- 1][a - 1] = c
    
def dijkstra(s):
    used = [False] * N
    for i in range(N):
        d[i] = INF
    d[s] = 0
    
    while True:
        v = -1
        for u in range(N):
            if used[u] == False and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        
        for u in range(N):
            d[u] = min(d[u], d[v] + cost[v][u])
            
Q, K = list(map(int, input().split()))
for _ in range(Q):
    ans = 0
    x, y = list(map(int, input().split()))
    dijkstra(x - 1)
    ans += d[K - 1]
    #print(d)
    dijkstra(K - 1)
    ans += d[y - 1]
    #print(d)
    print(ans)

# Optimized solution
import heapq

N = int(eval(input()))
d = [0] * N
INF = float('inf')

class Info:
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost
        
G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b, c = list(map(int, input().split()))
    G[a - 1].append(Info(b - 1, c))
    G[b - 1].append(Info(a - 1, c))
    
def dijkstra(s):
    for i in range(N):
        d[i] = INF
    d[s] = 0
    h = []
    heapq.heappush(h, [0, s])
    
    while h != []:
        p = heapq.heappop(h)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(G[v])):
            e = G[v][i]
            if d[e.to] > d[v] + e.cost:
                d[e.to] = d[v] + e.cost
                heapq.heappush(h, [d[e.to], e.to])

Q, K = list(map(int, input().split()))
for _ in range(Q):
    ans = 0
    x, y = list(map(int, input().split()))
    dijkstra(x - 1)
    ans += d[K - 1]
    #print(d)
    dijkstra(K - 1)
    ans += d[y - 1]
    #print(d)
    print(ans)
# Original solution
from collections import defaultdict
import heapq

N = int(eval(input()))
INF = float('inf')
edges = [list(map(int, input().split())) for _ in range(N-1)]
nodes = defaultdict(list)

for e in edges:
    nodes[e[0] - 1].append((e[2], e[1] - 1))
    nodes[e[1] - 1].append((e[2], e[0] - 1))


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

def dijkstra(x, y):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist[y]


for q in queries:
    x, y = q[0] - 1, q[1] - 1
    print((dijkstra(x, K - 1) + dijkstra(K - 1, y)))



# Optimized solution
from collections import defaultdict
import heapq

N = int(eval(input()))
INF = float('inf')
edges = [list(map(int, input().split())) for _ in range(N-1)]
nodes = defaultdict(list)

for e in edges:
    nodes[e[0] - 1].append((e[2], e[1] - 1))
    nodes[e[1] - 1].append((e[2], e[0] - 1))


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

def dijkstra(x):
    que = []
    heapq.heapify(que)
    dist = [INF for _ in range(N)]
    dist[x] = 0
    heapq.heappush(que, (0, x))

    while que:
        p = heapq.heappop(que)
        v = p[1]
        if dist[v] < p[0]:
            continue
        for e in nodes[v]:
            if dist[e[1]] > dist[v] + e[0]:
                dist[e[1]] = dist[v] + e[0]
                heapq.heappush(que, (dist[e[1]], e[1]))

    return dist

distk = dijkstra(K - 1)

for q in queries:
    x, y = q[0] - 1, q[1] - 1
    print((distk[x] + distk[y]))
# Original solution
from heapq import heappush, heappop
inf = float('inf')

# import: from heapq import heappush,heappop
# distの初期化: dist = [inf]*n; dist[start] = 0
def dijkstra(ad,dist,n,start):
    pq = [(0,start)]
    while pq:
        w,v = heappop(pq)
        for nw,nv in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(dist[nv],nv))

N = int(eval(input()))

ad = [[] for _ in range(N)]

for _ in range(N-1):
    a,b,c = list(map(int,input().split()))
    a -= 1;  b -= 1
    ad[a].append((c,b))
    ad[b].append((c,a))

Q,K = list(map(int,input().split()))
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

dist = [inf]*N
dist[K] = 0

dijkstra(ad,dist,N,K)

for x,y in query:
    ans = dist[x] + dist[y]
    print(ans)

# Optimized solution
from heapq import heappush, heappop
inf = float('inf')

# (始点,隣接リスト)
def dijkstra(start,ad):
    global dist
    dist = [inf]*len(ad)
    dist[start] = 0
    pq = [(start,0)]
    while pq:
        v = heappop(pq)[0]
        for nv,nw in ad[v]:
            if dist[nv] > dist[v] + nw:
                dist[nv] = dist[v] + nw
                heappush(pq,(nv,dist[nv]))

N = int(eval(input()))
ad = [[] for _ in range(N)]
for _ in range(N-1):
    a,b,c = list(map(int,input().split()))
    a -= 1; b -= 1
    ad[a].append((b,c))
    ad[b].append((a,c))
Q,K = list(map(int,input().split()))
K -= 1
query = [[int(e)-1 for e in input().split()] for _ in range(Q)]

dijkstra(K,ad)

for x, y in query:
    ans = dist[x] + dist[y]
    print(ans)
# Original solution
from heapq import heappop, heappush
n = int(eval(input()))
grid = [list(map(int, input().split())), list(map(int, input().split()))]


def biggest(grid, start, cost=0):
    dist = [[0 for _ in range(n)] for _ in range(2)]
    dx = [1, 0]
    dy = [0, 1]
    st = [(cost, start)]
    dist[start[0]][start[1]] = grid[start[0]][start[1]] + cost
    while(st):
        c, [sx, sy] = heappop(st)
        for a, b in zip(dx, dy):
            x = sx + a
            y = sy + b
            if x >= 2 or y >= n:
              continue
            dxy = dist[sx][sy] + grid[x][y]
            if dist[x][y] >= dxy:
                continue
            dist[x][y] = dxy
            heappush(st, (dist[x][y], [x, y]))
    return dist[-1][-1]


dist = biggest(grid, [0, 0], cost=0)
print(dist)

# Optimized solution
n = int(eval(input()))
grid = [list(map(int, input().split())), list(map(int, input().split()))]
dist = [[0 for _ in range(n)] for _ in range(2)]
dist[0][0] = grid[0][0]
for i in range(2):
  for j in range(n):
    if j < n - 1:
      dist[i][j + 1] = max(dist[i][j + 1], dist[i][j] + grid[i][j + 1])
    if i == 0:
      dist[1][j] = max(dist[1][j], dist[0][j] + grid[1][j])
print((dist[-1][-1]))
# Original solution


def third(n,q):
    n = int(n)
    q = float(q)
    if n == 1: return q/2
    else : return third(n-1,q)- (third(n-1,q)**3-q)/(3*third(n-1,q)**2)

kai = []
while(True):
    try:
        q = eval(input())
        if q == -1:
            break
        else :
            n = 1
            q = float(q)
            while  (abs(q-third(n, q)**3) >= 0.00001*q):
                n += 1
            print('{:.6f}'.format(third(n, q)))
    except EOFError:
        break

# Optimized solution
while(True):
    try:
        q = eval(input())
        if q == -1:
            break
        else :
            q = float(q)
            x = q/2
            while  (abs(q-x**3) >= 0.00001*q):
                x = x- (x**3-q)/(3*x**2)
            print('{:.6f}'.format(x))
    except EOFError:
        break
# Original solution
N, M = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
R = [0] * (N+1)

ans = 0
temp = 0

for i in range(N):
    R[i+1] = temp + A[i]
    temp = R[i+1]

for j in range(1,N+1):
    for d in range(1,N+1):
        if j - d >= 0:
            if (R[j] - R[j-d]) % M == 0:
                ans += 1
print(ans)

# Optimized solution
# coding: utf-8
# Your code here!
N, M = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
R = [0] * (N+1)
S = [0] * (N+1)
S_dict = {}

ans = 0
temp = 0

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

for s in S:
    if s in S_dict:
        S_dict[s] += 1
    else:
        S_dict[s] = 1

for v in list(S_dict.values()):
    ans += int(v*(v-1)/2)

print(ans)
# Original solution
from collections import Counter


N, M = [int(elem) for elem in input().split(' ')]
A_list = [int(elem) % M for elem in input().split(' ')]
assert len(A_list) == N

cuml_A_list = [0] * N
current_sum = 0
for i, A in enumerate(A_list):
    current_sum += A
    current_sum %= M
    cuml_A_list[i] = current_sum

counter = Counter(cuml_A_list)
total_count = 0
for key, value in list(counter.items()):
    if key == 0:
        total_count += value * (value - 1) // 2 + value
    else:
        total_count += value * (value - 1) // 2

print(total_count)


# Optimized solution
import sys
from collections import Counter
finput = sys.stdin.readline

N, M = [int(elem) for elem in finput().split(' ')]
A_list = [int(elem) % M for elem in finput().split(' ')]
assert len(A_list) == N

cuml_A_list = [0] * N
current_sum = 0
for i, A in enumerate(A_list):
    current_sum += A
    current_sum %= M
    cuml_A_list[i] = current_sum

counter = Counter(cuml_A_list)
total_count = 0
for key, value in list(counter.items()):
    if key == 0:
        total_count += value * (value - 1) // 2 + value
    else:
        total_count += value * (value - 1) // 2

print(total_count)
# Original solution
from collections import Counter

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

S = [0]
s = 0

for i in range(n):
  s += A[i]
  S += [s]

R = []

for i in range(n+1):
  R += [S[i]%m]
  
R = Counter(R)

ans = 0

for r in list(R.values()):
  ans += r*(r-1)//2

print(ans)

# Optimized solution
from collections import Counter

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

S = [0]

for i in range(N):
    S.append((S[-1]+A[i])%M)

C = Counter(S)

ans = 0

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

print(ans)
# Original solution
def comb1(n, r):
    if n == 0 or r == 0: return 1
    return comb1(n, r-1) * (n-r+1) / r 
N, M = list(map(int, input().split()))
A = [int(i) for i in input().split()]
# N, M = 10, 400000000
# A = [int(i) for i in '1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000'.split()]
surplus = {0:0}
res = 0
B = []
for i in range(1, N + 1):
    tmp = sum(A[:i])%M
    B.append(tmp)
    surplus[tmp] = 0
for i in B:
    surplus[i] += 1
for tmp_key in list(surplus.keys()):
    res += comb1(surplus[tmp_key], 2)

corner = surplus[0]
if corner == 0:
    res -= 1
else:
    res += corner
print((int(res)))

# Optimized solution
def comb1(n, r):
    if n == 0 or r == 0: return 1
    return comb1(n, r-1) * (n-r+1) / r 
N, M = list(map(int, input().split()))
A = [int(i) for i in input().split()]
# N, M = 10, 400000000
# A = [int(i) for i in '1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000'.split()]
surplus = {0:0}
res = 0
tmp = 0
B = []
for i in range(0, N):
    tmp += A[i]
    tmp %= M
    B.append(tmp)
    surplus[tmp] = 0
for i in B:
    surplus[i] += 1

for tmp_key in list(surplus.keys()):
    res += comb1(surplus[tmp_key], 2)

corner = surplus[0]
if corner == 0:
    res -= 1
else:
    res += corner
print((int(res)))
# Original solution
from collections import Counter as C
from itertools import accumulate as a
def inp():return list(map(int,input().split()))
n,m = inp()
print((sum([v*(v-1)//2+(0 if k else v)for k,v in list(C([x%m for x in a(inp())]).items())])))

# Optimized solution
from collections import Counter as C
from itertools import accumulate as a
def inp():return list(map(int,input().split()))
n,m = inp()
print((sum([v*(v-1)//2 for v in list(C([x%m for x in a([0]+inp())]).values())])))
# Original solution
from collections import Counter as C
from itertools import accumulate as a
def inp():return list(map(int,input().split()))
n,m = inp()
print((sum([v*(v-1)//2 for v in list(C([x%m for x in a([0]+inp())]).values())])))

# Optimized solution
from collections import Counter as C
from itertools import accumulate as a
def i():return list(map(int,input().split()))
n,m=i()
print((sum([v*(v-1)//2 for v in list(C([x%m for x in a([0]+i())]).values())])))
# Original solution
import sys
input=sys.stdin.readline

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    A=list(map(int,input().split()))
    dp=[[0 for i in range(N)] for j in range(N)]
    count = 0
    for i in range(N):
        dp[i][i]=A[i]
        dp[i][i]%=M
        if dp[i][i]==0:
            count+=1


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

    print(count)




# Optimized solution
import sys
input=sys.stdin.readline

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    A=list(map(int,input().split()))
    B=[0]*(N+1)
    count=0
    for i in range(N):
        B[i+1]=B[i]+A[i]
        B[i+1]%=M

    for b in B:
        c=B.count(b)
        count+=c-1
    print((count//2))
# Original solution
from collections import defaultdict
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
A[0] %= M
for i in range(N-1):
    A[i+1] += A[i]
    A[i+1] %= M
d = defaultdict(lambda:0)
d[0] = 1
ans = 0
for i in range(N):
    ans += d[A[i]]
    d[A[i]] += 1
print(ans)

# Optimized solution
N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
from collections import defaultdict
r = defaultdict(lambda:0)

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

ans = r[0]
for s in r:
    ans += (r[s]*(r[s]-1))//2

print(ans)
# Original solution
import math
from itertools import accumulate


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

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

accum_A = [0] + A
accum_A = list(accumulate(accum_A))

ans = 0

for i in range(n):
    for j in range(i+1,n+1):
#         print('l:{}, r:{}, sum:{}'.format(i,j,(accum_A[j]-accum_A[i])))
        if (accum_A[j]-accum_A[i]) % m == 0:
            ans += 1

print(ans)


# Optimized solution

import math
from itertools import accumulate

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

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


accum_A = [0] + A
accum_A = list(accumulate(accum_A))

mod_dic = {}

for i in accum_A:
    mod = i%m
    
    if mod in list(mod_dic.keys()):
        mod_dic[mod] += 1
    else:
        mod_dic[mod] = 1

ans = 0
    
for i in list(mod_dic.values()):
    if i >= 2:
        ans += combinations_count(i,2)
    
print(ans)