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

n, m = map(int, input().split())
a=list(map(int, input().split()))
s=[0]*(n+1)
for i in range(1, n+1):
    s[i]=s[i-1]+a[i-1]
dic={}
for i in range(n+1):
    tmp=s[i]%m
    if tmp in dic.keys():
        dic[tmp]+=1
    else:
        dic[tmp]=1
ans=0
for i in dic.values():
    ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a=list(map(int, input().split()))
    s=[0]*(n+1)
    for i in range(1, n+1):
        s[i]=s[i-1]+a[i-1]
    dic={}
    for i in range(n+1):
        tmp=s[i]%m
        if tmp in dic.keys():
            dic[tmp]+=1
        else:
            dic[tmp]=1
    ans=0
    for i in dic.values():
        ans+=i*(i-1)//2
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

l, r = map(int, input().split())

mod = 2020
for i in range(l, r, 1):
  for j in range(i + 1, r + 1, 1):
    a = (i * j) % 2019
    if a < mod:
      mod = a

print(mod)

### FIXED CODE ###

l, r = map(int, input().split())

mod = 2020
for i in range(l, r, 1):
  for j in range(i + 1, r + 1, 1):
    a = (i * j) % 2019
    if a == 0:
      mod = a
      break
    elif a < mod:
      mod = a
  else:
    continue
  break

print(mod)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [10**9 for i in range(N+1)]
dp[1] = 0
for i in range(2,N+1):
    a = 10**9
    for j in range(1,K+1):
        if i - j - 1 < 0:
            continue
        x = H[i-1-j] - H[i-1]
        if x < 0:
            x = -x
        a = min(dp[i-j]+x,a)
    dp[i] = a
print(dp[N])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
dp = [10**9 for i in range(N+1)]
dp[1] = 0
for i in range(2,N+1):
    a = 10**9
    for j in range(1,K+1):
        if i - j - 1 < 0:
            continue
        x = H[i-1-j] - H[i-1]
        if x < 0:
            x = -x
        a = min(dp[i-j]+x,a)
    dp[i] = a
print(dp[N])
### BUGGY CODE ###

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353

s = []
for l, r in lr:
    s += [i for i in range(l, r + 1)]

dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    for j in s:
        dp[i] += dp[max(i - j, 0)]
    dp[i] %= mod
print(dp[n])


### FIXED CODE ###

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]
mod = 998244353

dp = [0] * (n + 1)
acc = [0] * (n + 1)
dp[1], acc[1] = 1, 1
for i in range(2, n + 1):
    for l, r in lr:
        dp[i] += acc[max(i - l, 0)]
        dp[i] -= acc[max(i - (r + 1), 0)]
    dp[i] %= mod
    acc[i] = (dp[i] + acc[i - 1]) % mod
print(dp[n])
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**10]*n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            if i + j < n and dp[i] + abs(h[i] - h[i+j]) < dp[i+j]:
                dp[i+j] = dp[i] + abs(h[i] - h[i+j])
    print(dp[n-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9+1]*n
    dp[0] = 0
    for i in range(1, n):
        buf = [dp[j] + abs(h[j]-h[i]) for j in range(max(i-k,0), i)]
        dp[i] = min(buf)
    print(dp[n-1])

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

N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
first = 1
while ng-ok > 1:
    tgt = (ok+ng)//2
    if first == 1:
        tgt == 4
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(0, k+1):
        for j in range(0, k+1):
                for l in range(0, k+1):
                        if i + j + l == s:
                                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(0, k+1):
        for j in range(0, k+1):
                if 0 <= s-i-j <= k:
                        count += 1
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False]
p = []
for i in range(m):
    p.append(list(map(int, input().split())))
l = [set() for i in range(n+1)]
for pi in p: 
    l[pi[0]].add(pi[1])
    l[pi[1]].add(pi[0])

while True:
  ans = able.count(True)
  able = [False]*(n+1)
  for i in range(1,n+1):
    ab = 0
    for j in l[i]:
      if s[j-1] == "A":
        ab |= 1
      else:
        ab |= 2
      if ab == 3:
        able[i] = True
        break
  for i in range(1,n+1):
    for j in l[i].copy():
      if not able[j]:
        l[i].remove(j)
  tmp = able.count(True)
  if ans == tmp:
    break
if any(able):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")
### BUGGY CODE ###

import bisect
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a.sort()
  tmp = deque([])
  for i in range(m):
    l,r = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= sorted(tmp,key=lambda tmp: tmp[1],reverse =True)
  ans = 0
  while tmp:
    if len(a) == 0:
      break
    b,c = tmp.pop(0)
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        a = a[min(1+place,b)::]
        ans += c*(min(1+place,b))
    #print(a)
  while a:
    ans += a.pop(0)
  print (ans)
solve()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a = deque(sorted(a))
  tmp = deque([])
  for i in range(m):
    r,l = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= deque(sorted(tmp,reverse =True))
  ans = 0
  while tmp:
    c,b = tmp.popleft()
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        if len(a) == 0:
           break
        for i in range(min(1+place,b)):
           a.popleft()
        ans += c*(min(1+place,b))
    #print(a)
  if a:
   ans += sum(a)
  print (ans)
solve()
### BUGGY CODE ###

x, y, z, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

d = [e1+e2 for e1 in a for e2 in b]
d.sort(reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]
e.sort(reverse=True)

for i in range(k):
  print(e[i])

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])
### BUGGY CODE ###

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

b=0
c=10**10
for i in range(1,n):
  b=abs(sum(a[:i])-sum(a[i:]))
  if b<c:
    c=b
print(c)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
tot=sum(a)
b=0
c=10**10
d=0
for i in range(n):
  b+=a[i]
  d=abs(tot/2 - b)
  if d<c:
    c=d
print(int(2*c))
### BUGGY CODE ###

S = str(input())
S_len = len(S)

DP = [[0 for j in range(13)] for i in range(S_len + 1)]
DP[S_len][0] = 1

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if S[i] != "?":
        for j in range(13):
            DP[i][(j + int(S[i]) * num) % 13] += DP[i + 1][j] % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                DP[i][(j + k * num) % 13] += DP[i + 1][j] % 1000000007

print(DP[0][5] % 1000000007)


### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

X = [[0] * N for i in range(61)]
for i, a in enumerate(A):
    for j in range(61):
        if (1 << j) & a:
            X[j][i] = 1

for i in range(61):
    X[i] = list(accumulate((X[i])))


ans = 0
for i, a in enumerate(A):
    for j in range(61):
        x = X[j][-1] - X[j][i]
        if (1 << j) & a:
            ans += (1 << j) * ((N - i - 1) - x)
            ans %= MOD

        else:
            ans += (1 << j) * x
            ans %= MOD


print(ans % MOD)


### FIXED CODE ###

def main():
    def accumulate(array):
        for i in range(len(array) - 1):
            array[i + 1] += array[i]
        return array

    N = int(input())
    A = list(map(int, raw_input().split()))
    MOD = 10 ** 9 + 7

    X = [[0] * N for i in range(61)]
    for i, a in enumerate(A):
        for j in range(61):
            if (1 << j) & a:
                X[j][i] = 1

    for i in range(61):
        X[i] = accumulate(X[i])


    ans = 0
    for i, a in enumerate(A):
        for j in range(61):
            x = X[j][-1] - X[j][i]
            if (1 << j) & a:
                ans += ((1 << j) % MOD) * ((N - i - 1) - x)
                ans %= MOD

            else:
                ans += ((1 << j) % MOD) * x
                ans %= MOD


    print(ans % MOD)


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

# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

dp[0] = 1

for v in range(1,N+1):
    if v in A:
        continue
    dp[v] = (dp[v] + dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v] + dp[v-2])%(1000000007)
print(dp[N])

### FIXED CODE ###

# C - Typical Stairs
N,M = map(int,input().split())
A = [int(input()) for _ in range(M)]
A = set(A)

# dp[i]: i 段目まで来た時の移動方法の総数
dp = [0]*(N+1)

# 初期条件
dp[0] = 1

for v in range(1,N+1):
    if v in A:
        continue
    dp[v] = (dp[v] + dp[v-1])%(1000000007)
    if v > 1:
        dp[v] = (dp[v] + dp[v-2])%(1000000007)
print(dp[N])
### BUGGY CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        K, S = map(int, input().split())
        ans = 0
        for i in range(K + 1):
            for j in range(K + 1):
                for k in range(K + 1):
                    if i + j + k == S:
                        ans += 1
        print(ans)

if __name__ == '__main__':
    AtCoder().main()

### FIXED CODE ###

import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        K, S = map(int, input().split())
        ans = 0
        for i in range(K + 1):
            for j in range(K + 1):
                Z = S - i - j
                if 0 <= Z <= K:
                    ans += 1
        print(ans)


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

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for i in range(m)]
dp = [1]*2 + [0 for _ in range(n-1)]
mod = 1000000007
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit() 
    
for i in range(n-1):
  if i+1 in a:
    dp[i+1] = 0
  dp[i+2] = dp[i]+dp[i+1]
  
  if dp[i+2] >= mod:
    dp[i+2] %= mod

print(dp[-1]%mod)  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)



def dfs(v, dist, memo):
    memo[v] = dist
    for nv in graph[v]:
        if memo[nv] >= 0:
            continue
        dfs(nv, dist+1, memo)


memo = [-1] * n
dfs(0, 0, memo)

node = 0
dist = 0
for i in range(n):
    if memo[i] > dist:
        dist = memo[i]
        node = i


memo = [-1] * n
dfs(node, 0, memo)

dist = max(memo)
count = dist + 1

dp = [0] * (count + 10)
dp[0] = 0
dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 1


if count >= 5:
    for i in range(5, count+1):
        if dp[i-2] == 1 and dp[i-1] == 1:
            dp[i] = 0
        else:
            dp[i] = 1

if dp[count]:
    print("First")
else:
    print("Second")



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


def dfs(v, dist, memo):
    memo[v] = dist
    for nv in graph[v]:
        if memo[nv] >= 0:
            continue
        dfs(nv, dist+1, memo)

memo = [-1] * n
dfs(0, 0, memo)

node = 0
dist = 0
for i in range(n):
    if memo[i] > dist:
        dist = memo[i]
        node = i

memo = [-1] * n
dfs(node, 0, memo)

dist = max(memo)
count = dist + 1

dp = [0] * (count + 10)
dp[0] = 0
dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 1


if count >= 5:
    for i in range(5, count+1):
        if dp[i-2] == 1 and dp[i-1] == 1:
            dp[i] = 0
        else:
            dp[i] = 1

if dp[count]:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

S = input()

ct = 0
while True:
    ct += S.count('01')
    S = S.replace('01', '')
    ct += S.count('10')
    S = S.replace('10', '')
    if not S.count('01') and not S.count('10'):
        break

print(ct*2)


### FIXED CODE ###

S = input()

red = S.count('0')
blue = S.count('1')

print(2*(min(red, blue)))
### BUGGY CODE ###

import sys

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

MOD = 10**9+7

debug = False

if debug:
    n = 50000
    A = list(range(n))
else:
    n,*A = get_all_int()




# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)

ans = 0

for a in A:
    a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

    for i in range(60):
        ans += 2**i * abs(bits[i] - a_bits[i]*n)

    # a_dash = list(map(lambda a: a*(n-1), a_bits))

    # log("a_dash", a_dash)

    # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
    # log("bits_dash", bits_dash)
    # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

    # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

    # for i in range(60):
    #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
    # log(a, ans)

print(ans//2 % MOD)


### FIXED CODE ###

import sys
import time

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def int_to_bits(x):
    return [ 1 if 2**i & x != 0 else 0 for i in range(60) ]

def inv(x, MOD):
    return pow(x, MOD-2, MOD)

start = time.time()

MOD = 10**9+7

debug = False

if debug:
    n = 30 * 10000
    A = list(range(n))
else:
    n,*A = get_all_int()

# ビットごとの出現回数 2**i
bits = [0] * 60

for a in A:
    for i in range(60):
        if 2**i & a != 0:
            bits[i] += 1

# log("bits:", bits)
# log("bits.", time.time() - start)

# ans = 0

ans = sum(( pow(2, i, MOD) * bits[i] * (n-bits[i]) for i in range(60))) % MOD

# for a in A:
#     # a_bits = [ 1 if 2**i & a != 0 else 0 for i in range(60) ]

#     for i in range(60):
#         ans += 2**i * abs(bits[i] - (1 if 2**i & a != 0 else 0) *n)

#     # a_dash = list(map(lambda a: a*(n-1), a_bits))

#     # log("a_dash", a_dash)

#     # bits_dash = [ bits[i] - a_bits[i] for i in range(60)]
#     # log("bits_dash", bits_dash)
#     # ans += sum( ( 2**i * abs(bits_dash[i]-2*a_dash[i])) for i in range(60) )

#     # ans += sum( ( 2**i * abs(bits[i]-2*a_dash[i])) for i in range(60) )

#     # for i in range(60):
#     #     ans = (ans + 2**i * abs(bits_dash[i] - a_dash[i])) % MOD
#     # log(a, ans)

# print(ans//2 % MOD)
print(ans)
# log("end.", time.time() - start)
### BUGGY CODE ###

n, k = [int(v) for v in input().split()]
h = [int(v) for v in input().split()]

INF = 10 ** 15
dp = [INF] * n
dp[0] = 0

for i in range(n - 1):
    for j in range(i + 1, min(i + k+1, n)):
        dp[j] = min(dp[j], dp[i]+abs(h[i] - h[j]))

print(dp[n - 1])


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

for i in range(1, n):
    hi = h[i]
    s = max(i-k,0)
    dp[i] = min(dpj + abs(hi - hj) for dpj, hj in zip(dp[s:i], h[s:i]))
    
print(dp[-1])
### BUGGY CODE ###

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

count = 0
i = 0
while x * i <= b:
    if x * i >= a:
        count += 1
    i += 1

print(count)

### FIXED CODE ###

import math
from decimal import Decimal
a, b, x = map(int, input().split())
a, b, x = Decimal(a), Decimal(b), Decimal(x)

min_bai = math.ceil(a/x)  # xの倍数で最小
max_bai = math.floor(b/x)  # xの倍数で最大
x_bai = max_bai - min_bai + 1

# print(min_bai)  # debug
# print(max_bai)  # debug
print(x_bai)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a
if ans > 10 ** 18:
    ans = -1
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
    print(0)
else:
    for a in A:
        ans *= a
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

ans = 0

for i in range(n):
    if s[i] == "R":
        r.append(i)
    if s[i] == "G":
        g.append(i)
    if s[i] == "B":
        b.append(i)

for i in r:
    for j in g:
        for k in b:
            li = [i,j,k]
            li.sort()
            if li[1]-li[0]==li[2]-li[1]:
                continue
            else:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k<n and s[k] != s[i] and s[k] != s[j] and s[i] != s[j]:
            ans -= 1

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

h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            while stack:
                nowi,nowj=stack.popleft()
                grid[nowi][nowj]=col
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
es=[set([]) for _ in range(col)]
visited=[-1]*col
for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])

### FIXED CODE ###

h,w=map(int, input().split())
ch,cw=map(int, input().split())
ch-=1
cw-=1
dh,dw=map(int, input().split())
dh-=1
dw-=1
grid=[]
for i in range(h):
    s=list(input())
    news=[-1 if x=='#' else 0 for x in s]
    grid.append(news)
dif=[(1,0),(-1,0),(0,1),(0,-1)]
from collections import deque
col=0
for i in range(h):
    for j in range(w):
        if grid[i][j]==0:
            col+=1
            stack=deque([(i,j)])
            grid[i][j]=col
            while stack:
                nowi,nowj=stack.popleft()
                for di,dj in dif:
                    if 0<=nowi+di<h and 0<=nowj+dj<w and grid[nowi+di][nowj+dj]==0:
                        stack.append((nowi+di,nowj+dj))
                        grid[nowi+di][nowj+dj]=col
start=grid[ch][cw]-1
end=grid[dh][dw]-1
if start==end:
    print(0)
    exit()
es=[set([]) for _ in range(col)]
visited=[-1]*col

for i in range(h):
    for j in range(w):
        now=grid[i][j]
        if now!=-1: 
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if 0<=i+x<h and 0<=j+y<w:
                        nex=grid[i+x][j+y]
                        if nex!=-1 and now!=nex:
                            es[now-1].add(nex-1)

stack=deque([start])
visited[start]=0
while stack:
    now=stack.popleft()
    for e in es[now]:
        if visited[e]==-1:
            visited[e]=visited[now]+1
            stack.append(e)
#print(grid)
print(visited[end])
### BUGGY CODE ###

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

def gcd(x,y):
  if x<y:
    x,y=y,x
  while x%y!=0:
    x,y=y,x%y
  return y

def lcm(x,y):
  return x*y//gcd(x,y)

block=lcm(c,d)
block_c=block//c
block_d=block//d
ans_in_block=block-(block_c+block_d-1)

def count_ans(z,block,ans_in_block,p,q):
  z_amari=z%block
  z_ans=0
  for i in range(1,z_amari+1):
    if i%p!=0 and i%q!=0:
      z_ans+=1
  return (z//block)*ans_in_block+z_ans

print(count_ans(b,block,ans_in_block,c,d)-count_ans(a,block,ans_in_block,c,d)+(a%c!=0 and a%d!=0))  


### FIXED CODE ###

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

def gcd(x,y):
  if x<y:
    x,y=y,x
  while x%y!=0:
    x,y=y,x%y
  return y

def lcm(x,y):
  return x*y//gcd(x,y)

a_ans=(a-1)-(a-1)//c-(a-1)//d+(a-1)//lcm(c,d)
b_ans=b-b//c-b//d+b//lcm(c,d)
print(b_ans-a_ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
S = [0 for _ in range(N + 1)]
for i in range(1, N + 1):
    S[i] = S[i - 1] + A[i - 1]
ans = 0
for l in range(N):
    for r in range(l, N):
        s = S[r + 1] - S[l]
        if s % M == 0:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
A = list(map(int, input().split()))
S = [0 for _ in range(N + 1)]
MOD = defaultdict(int)
for i in range(1, N + 1):
    S[i] = S[i - 1] + A[i - 1]
for n in S:
    MOD[(n % M)] += 1
ans = 0
for key in MOD:
    n = MOD[key]
    ans += n * (n - 1) // 2
print(ans)