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

k = int(input())
val = 7
if k%2 == 0:
    ans = -1
else:
    for i in range(1,10**12+1):
        if val >= k:
            sub = val % k
            if sub == 0:
                  ans = i
                  break
            else:
                  val = 10 * sub + 7
        else:
            val = 10 * val + 7
print(ans)

### FIXED CODE ###

k = int(input())
val = 7
if k%2 == 0:
    ans = -1
elif k%5 == 0:
    ans = -1
else:
    for i in range(1,10**12+1):
        if val >= k:
            sub = val % k
            if sub == 0:
                  ans = i
                  break
            else:
                  val = 10 * sub + 7
        else:
            val = 10 * val + 7
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
cnt = 0
l = list(map(int, input().split()))
for a, b, c in itertools.combinations(l, 3):
    if a < b + c and b < a + c and c < a + b:
        cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
cnt = 0
l = sorted(list(map(int, input().split())))
for a in range(n - 2):
    for b in range(a + 1, n - 1):
        c_min = b + 1
        c_max = bisect.bisect_left(l, l[a] + l[b]) - 1
        cnt += c_max - c_min + 1
print(cnt)
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline
import numpy as np

def main():
    s = str(input())
    l = len(s)
    dp = np.zeros((2,13),dtype=int)
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for st in s:
        for j in range(13):
            if st != "?":
                num = int(st)
                dp[use][(j*10+num)%13] = dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5]%MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

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

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = rl()
MOD = 10 ** 9 + 7
#1番目以降(N個の数)のbitの格桁の合計
l = np.array([0] * 60)
for i in range(N):
    s = np.array(list(map(int, list(str(bin(A[i]))[2:].rjust(60, '0')))))
    #print(s)
    l = l + s
l2 = np.array([0] * 60)
#print(l)
for i in range(N-1):
    s = np.array(list(map(int, list(str(bin(A[i]))[2:].rjust(60, '0')))))
    x = N - 1 - i
    l -= s
    l2 += s * (x-l)
    l2 += (1-s) * l
    
answer = 0
#print(l2)
l2 = l2.tolist()
for i in range(60):
    answer += 2 ** (59-i) * l2[i]
    answer %= MOD
#print(l)
print(answer)



### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = np.array(rl())
answer = 0
MOD = 10 ** 9 + 7

for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x *= 2
        x %= MOD
    answer += x

print(answer%MOD)
### BUGGY CODE ###

N, W = [int(x) for x in input().split()]

w, v = [], []
MAX_V = 100001
INF = 1000000000001

for i in range(N):
  wi, vi = [int(x) for x in input().split()]
  w.append(wi)
  v.append(vi)

dp = []
for i in range(N+1):
  dp.append([INF] * MAX_V)

dp[0][0] = 0

for i in range(N):
  for sum_v in range(MAX_V):
    if sum_v - v[i] >= 0:
      dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
      
    dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


res = 0
for sum_v in range(MAX_V):
  if dp[N][sum_v] <= W:
    res = sum_v
  
print(res)

### FIXED CODE ###

N, W = [int(x) for x in input().split()]

w, v = [], []
MAX_V = 100001
INF = 1000000000001

for i in range(N):
  wi, vi = [int(x) for x in input().split()]
  w.append(wi)
  v.append(vi)

dp = []
for i in range(N+1):
  dp.append([INF] * MAX_V)

dp[0][0] = 0

for i in range(N):
  for sum_v in range(MAX_V):
    if sum_v - v[i] >= 0:
      dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
      
    dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])


res = 0
for sum_v in range(MAX_V):
  if dp[N][sum_v] <= W:
    res = sum_v
  
print(res)
### BUGGY CODE ###

def get_prime_list(n):
    L = list(range(2,n+1))
    for i in range(2,int((n+1)**0.5)):
        if i not in L:
            continue
        L = [j for j in L if j <= i] + [j for j in L if j > i and j % i != 0]
    return L

Q = int(input())
lr = [list(map(int,input().split())) for _ in range(Q)]
prime_list = get_prime_list(100000)
like_num = [i for i in prime_list if (i+1)//2 in prime_list]
for l,r in lr:
    print(len([i for i in like_num if l<=i<=r]))

### FIXED CODE ###

def get_prime_list(n):
    L = tuple(range(2,n+1))
    for i in range(2,int((n+1)**0.5)):
        if i not in L:
            continue
        L = tuple(j for j in L if j <= i) + tuple(j for j in L if j > i and j % i != 0)
    return L

Q = int(input())
lr = [tuple(map(int,input().split())) for _ in range(Q)]
prime_list = get_prime_list(100000)
like_num = tuple(i for i in prime_list if (i+1)//2 in prime_list)
L = [0] * 100002
for i in range(3,100001,2):
    if i in like_num:
        L[i] = L[i-2]+1
    else:
        L[i] = L[i-2]
for l,r in lr:
    print(L[r]-L[l-2])
### BUGGY CODE ###

N,Q = map(int,input().split(' '))
S = input()
#文字列のパターン
pattern = 'AC'

for x in range(Q):
  l,r = map(int, input().split(' '))
  S_fragment = S[l-1:r]
  print(S_fragment.count(pattern))

### FIXED CODE ###

N,Q = map(int,input().split(' '))
S = input()
#文字列のパターン
pattern = 'AC'
X = [0] * (N+1)

for i in range(N):
  X[i+1] = X[i] +(1 if S[i:i+2] =='AC' else 0)

for j in range(Q):
  l,r = map(int, input().split(' '))
  print(X[r-1]-X[l-1])
### BUGGY CODE ###

class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        self.__size = size
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, l: int, r: int)->int:
        """(l, r] の累積和を計算する。
        :param l: left index
        :param r: right index
        :return: (l, r] の累積和
        """
        return self.__sum__(r) - self.__sum__(l)

    def __sum__(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A:
        s += bit.sum(0, a)
        bit.add(a, 1)

    return s


def check2(A: list, x: int)->int:
    n = len(A)
    S = [0] * (n + 1)
    for i in range(n):
        if x <= A[i]:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    m = min(S)
    return inversion([s - (m - 1) for s in S])


def median_of_medians(N: int, A: list) -> int:
    def check(x: int)->int:
        S = [0] * (N + 1)
        for i in range(N):
            if x <= A[i]:
                S[i + 1] = S[i] + 1
            else:
                S[i + 1] = S[i] - 1
    
        m = min(S)
        return inversion([s - (m - 1) for s in S])

    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(alpha[m]) >= (N * (N + 1)) // 2:
            l = m
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)


### FIXED CODE ###


def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
### BUGGY CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
def my_index(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)
dic={}
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]]={i}
    else:
        dic[s[i]].add(i)
b=0
ans=0
for i in range(m):
    if t[i] not in dic:
        print(-1)
        exit()
    ind=my_index(s[b:],t[i])
    if ind==-1:
        ind=my_index(s,t[i])+1
        ans+=n-b+ind
        b=ind
    else:
        ans+=ind+1
        b+=ind+1
print(ans)
    

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
s=list(input())
n=len(s)
t=input()
m=len(t)
dic={}
ans=0
for i in range(len(s)):
    if s[i] not in dic:
        dic[s[i]]=[i]
    else:
        dic[s[i]].append(i)
b=-1
for i in range(m):
    if t[i] not in dic:
        print(-1)
        exit()
    res=dic[t[i]]
    if res[-1]<=b:
        ans+=res[0]+1+(n-b-1)
        b=res[0]
    else:
        idx=bisect.bisect_right(res,b)
        ans+=res[idx]-b
        b=res[idx]
print(ans)
### BUGGY CODE ###

from collections import Counter
def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

cities = Counter()

routes = {}
for _ in range(m):
    a, b, c = read_line(int, int, int)

    cities[a] = 1
    cities[b] = 1

    if a in routes:
        routes[a][b] = c
    else:
        routes[a] = { b : c }

    if b in routes:
        routes[b][a] = c
    else:
        routes[b] = { a : c }

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        if a in routes and b in routes[a]:
            c += routes[a][b]
        else:
            c += 100000 + 1
    return c

def passing_all_cities(selected):
    for r in rs:
        if r not in selected:
            return False
    return True


smallest = 100000 + 1

def f(selected, rest):
    global smallest
    if passing_all_cities(selected):
        c = cost(selected)
        if smallest > c:
            smallest = c
    else:
        for i in range(len(rest)):
            r = rest[i]
            rest_copy = rest[:]
            del rest_copy[i]
            if cost(selected + [r]) <= smallest:
                f(selected + [r], rest_copy)

f([], list(cities.keys()))
print(smallest)


### FIXED CODE ###

from itertools import permutations

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, m, r = read_line(int, int, int)

rs = [int(r) for r in input().split()]

costs = {}
for i in range(n + 1):
    costs[i] = {}
    for j in range(n + 1):
        costs[i][j] = float('inf')

for _ in range(m):
    a, b, c = read_line(int, int, int)

    costs[a][b] = costs[b][a] = c

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            c = costs[i][k] + costs[k][j]
            if costs[i][j] > c:
                costs[i][j] = c

def cost(selected):
    c = 0
    for i in range(len(selected) - 1):
        a = selected[i]
        b = selected[i + 1]
        c += costs[a][b]
    return c

smallest = float('inf')

for p in permutations(rs):
    c = cost(p)
    if smallest > c:
        smallest = c

print(smallest)
### BUGGY CODE ###

a, b, k = map(int, input().split())
n = range(a, b+1)
for i in n:
  if i in sorted(set(n[:k]) | set(n[-k:])):
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
n = range(a, b+1)
for i in sorted(set(n[:k]) | set(n[-k:])):
  print(i)
### BUGGY CODE ###

def comb(n,r):
    r=min(r,n-r)
    h,k=1,1
    for i in range(1,r+1):
        h*=(n-r+i)
        k*=i
    return h//k
from bisect import bisect_left as bl,bisect_right as br
n=int(input())
l=list(map(int,input().split()))
l.sort()
mm=l[-1];ans=0;p=0
for i in range(max(0,bl(l,l[-1]//2)-2),min(n,l[-1]//2+3)):
    g=comb(mm,l[i])
    if ans<g:
        ans=g
        p=i
print(mm,l[p])


### FIXED CODE ###

from bisect import bisect_left as bl,bisect_right as br
n=int(input())
l=list(map(int,input().split()))
l.sort()
pre=10**9
mm=l[-1];p=0
for i in range(max(0,bl(l,l[-1]//2)-2),min(n,l[-1]//2+3)):
    if abs(mm/2-l[i])<pre:pre=abs(mm/2-l[i]);p=i
print(mm,l[p])
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

X_max = 0
X_min = 0

nCr = {}

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


for i in range(N-K+1):
    n = cmb(N-1-i, K-1)
    X_max += n*A[-(i+1)]
    X_min += n*A[i]

print((X_max - X_min) % 1000000007)

### FIXED CODE ###

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

p = 1000000007
X_max = 0
X_min = 0


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


for i in range(N-K+1):
    n = cmb(N-1-i, K-1, p)
    X_max += n*A[-(i+1)]
    X_max %= p
    X_min += n*A[i]
    X_min %= p

print(int((X_max - X_min) % p))
### BUGGY CODE ###

n=int(input())
a=[0]*n
ans2=[0]*n
ans1=[0]*n
a=list(map(int,input().split()))
List=[i for i in range(1,n+1)]

ans1=[List[i]+a[i] for i in range(n)]
ans2=[List[i]-a[i] for i in range(n)]

#print(ans1)
#print(ans2)
al1=max(ans1)
al2=max(ans2)
al=max(al1,al2)
ans=0
for i in range(al):
  if (ans1.count(i)>0 and ans2.count(i)>0):
    ans+=ans1.count(i)*ans2.count(i)
print(ans)

### FIXED CODE ###

n=int(input())
a=[0]*n
a=list(map(int,input().split()))
L={}
R={}
ans=0
for i in range(n):
    L.setdefault(i-a[i],0)
    R.setdefault(i+a[i],0)
    L[i-a[i]]+=1
    R[i+a[i]]+=1
    
    if (i-a[i] in R):
        ans+=R[i-a[i]]
        #print(ans,L[i-a[i]])
    if (i+a[i] in L):
        ans+=L[i+a[i]]

print(ans)
#print(L)
#print(R)
### BUGGY CODE ###

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

t = list(map(int,input().split()))
ab=[]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a,b])

t.sort(reverse=True)
ab = sorted(ab, key=lambda x: -x[1])
res = []
x = t.pop(0)

for i, j in ab:
    #print(res, i, j)
    while j < x:
        res.append(x)
        if len(t):
            x = t.pop(0)
        else:
            x = 0
    for _ in range(i):
        res.append(j)
        if len(res) >= n:
            break
    if len(res) >= n:
        break

if len(res) < n:
    for i in range(n):
        res.append(x)
        x = t.pop(0)
        if len(res) >= n:
            break
        

print(sum(res[0:n]))

### FIXED CODE ###

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

t = list(map(int,input().split()))
ab=[]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a,b])

t.sort(reverse=True)
ab = sorted(ab, key=lambda x: -x[1])
count = 0
for i,j in ab:
    t += [j]*i
    count += i
    if n <= count:
        break

t.sort(reverse=True)
        
print(sum(t[:n]))
### BUGGY CODE ###

def nCr(n,r):
    if r*2>n:
        return nCr(n,n-r)
    mod = 10 ** 9 + 7
    a = b = 1
    for i in range(r):
        a = (a * (n - i)) % mod
        b = (b * (r - i)) % mod
    return (a * pow(b,mod-2,mod))%mod

N,K = map(int,input().split())
cnt = 0
tmp = [i for i in range(N+1)]
for i in range(K,N+2):
    cnt += sum(tmp[-i:])-sum(tmp[:i])+1

print(cnt)

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    ans = 0
    souwa = N*(N+1)//2
    mod = 10 ** 9 + 7

    for i in range(K,N+2):
        mi = (i-1)*i//2
        ma = souwa - (N-i)*(N-i+1)//2
        ans += ma-mi+1

    print(ans%mod)

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

_in = list(open(0))
h, w = list(map(int, _in[0].split()))

s = []
for i, y in enumerate(_in[1:]):
    for j, x in enumerate(y):
        if x == '#':
            s.append((i+1,j+1))

a = [[False]*(w+2)]
a += [[False] + [True]*w + [False] for _ in range(h)]
a += [[False]*(w+2)]

ans = -1
while s:
    ns = []
    for i, j in s:
        a[i][j] = False

        if a[i-1][j]:
            a[i][j] = False
            ns.append((i-1, j))
        if a[i+1][j]:
            a[i][j] = False
            ns.append((i+1, j))
        if a[i][j-1]:
            a[i][j] = False
            ns.append((i, j-1))
        if a[i][j+1]:
            a[i][j] = False
            ns.append((i, j+1))
        
    s = ns
    ans += 1
    
print(ans)

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

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

S = input()
Q = int(input())
Ss = S
q = []
for _ in range(Q):
    q.append(list(map(str,input().rsplit())))
for i in range(Q) :
    if int(q[i][0]) == 1 :
        Ss = Ss[::-1]
    else:
        if int(q[i][1]) == 1 :
            Ss = str(q[i][2]) + Ss
        else:
            Ss = Ss + str(q[i][2])
print(Ss)

### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = []
for i in range(1000000, 1000000 + n):
    x.append(i + 1)
for j in range(n):
    x.remove(a[j] + 1000000)
    x.insert(a[j] - 1, j + 1)
print(" ".join(map(str, x)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = []
for i in range(n):
    x.append((a[i], i + 1))
x.sort()
y = []
for i in range(n):
    y.append(x[i][1])
print(" ".join(map(str, y)))
### BUGGY CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

# TLE
# Amod = [A for A in map(lambda x: int(x) % M , input().split())]
# ans = 0
# for l in range(len(Amod)):
#     acm = 0
#     for r in range(l, len(Amod)):
#         acm = (acm + Amod[r]) % M
#         if acm == 0: ans += 1

Asym = []
sym = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    Asym.append(sym)
# print(Asym)
    
ans = Asym.count(0)
for sym in set(Asym):
    cnt = Asym.count(sym)
    ans +=  int(cnt * (cnt -  1) / 2)

print(ans)


### FIXED CODE ###

# encoding: utf-8
N, M = list(map(int, input().split()))

d_sym = {}
sym = 0

# refresh

ans = 0
for A in map(int, input().split()):
    sym = (sym + A) % M
    #
    if sym == 0: ans += 1
    # 
    if str(sym) in d_sym.keys(): d_sym[str(sym)] += 1
    else: d_sym[str(sym)] = 1

print(int(ans + sum([val * (val - 1) / 2 for val in d_sym.values()])))
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split())))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        k = bisect_left(l[j:], l[i] + l[j]) + j
        ans += k - j - 1
print(ans)

### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        k = bisect_left(l,l[i]+l[j])
        ans += k - j - 1

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

s=input()
q=int(input())
for i in range(q):
    a=list(map(str,input().split()))
    if a[0]=="1":
        s=s[::-1]
    if a[0]=="2":
        if a[1]=="1":
            s=a[2]+s
        if a[1]=="2":
            s=s+a[2]           
print(s)

### FIXED CODE ###

s=input()
q=int(input())
mae=""
usr=""
flg=True
for i in range(q):    
    a=list(map(str,input().split()))
    if a[0]=="1":
        if flg:
            flg=False
        elif flg==False:
            flg=True
    if a[0]=="2":
        if a[1]=="1":
            if flg:
                mae=a[2]+mae
            else:
                usr=usr+a[2]
        if a[1]=="2":
            if flg:
                usr=usr+a[2]
            else:
                mae=a[2]+mae
if flg:
    ans=mae+s+usr
else:
    ans=usr[::-1]+s[::-1]+mae[::-1]
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
S.append(input())
for i in range(N-1):
    p = input()
    q = 0
    for k in range(len(S)):
        #print(len(S))
        #print(S)
        if p == S[k]:
            q = 1
    if q == 0:
        S.append(p)
print(len(S))
#print(S)

### FIXED CODE ###

N = int(input())
S = set()
for i in range(N):
    S.add(input())
print(len(S))
### BUGGY CODE ###

n = int(input())
numlist = input().split()

for i in range(1, n + 1):
	#	print(i)
	print(numlist.count(str(i)))


### FIXED CODE ###

n = int(input())
numlist = list(map(int, input().split()))
# print(numlist)
result = [0] * n
# print(result)

for i in numlist:
	result[i - 1] = result[i - 1] + 1

for j in range(len(result)):
	print(result[j])
# for i in range(1, n + 1):
#	print(numlist.count(i))
### BUGGY CODE ###

#TLE
import sys
n = int(input())
a = list(map(int, input().split()))
postCenter=dif=0
tmp = 2020202020
for i in range(n):
    if tmp > abs(sum(a[:i])-sum(a[i:])):
        tmp = abs(sum(a[:i])-sum(a[i:]))
        if tmp == 0:
            print(tmp)
            exit()
print(tmp)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
tmp=sys.maxsize
s = sum(a)
t = 0
for i in range(n):
    t += a[i]
    tmp = min(tmp,abs(s-t*2))
print(tmp)
### BUGGY CODE ###

N = int(input())

P = [i for i in range(1, N)]
print(sum(P))

### FIXED CODE ###

N = int(input())

print(N*(N-1)//2)