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

import collections


def p_c():
    n = int(input())
    ans = 0

    l = [collections.Counter(input()) for _ in range(n)]

    for i in range(n):
        for j in range(i + 1, n):
            if l[i] == l[j]:
                ans += 1

    print(ans)


if __name__ == '__main__':
    p_c()


### FIXED CODE ###

from collections import Counter

def p_c():
    n = int(input())
    ans = 0

    l = ["".join(sorted(input())) for _ in range(n)]

    a = Counter(l).values()

    for i in a:
        ans += sum(range(i))

    print(ans)
    
    
if __name__ == '__main__':
    p_c()
### BUGGY CODE ###

n,a,b = map(int,input().split())
tama = 0
blue = 0
for i in range(10**100):
    if tama <= n:
        if tama + a >= n:
            blue += (n - tama)
            break
        tama += a
        blue += a

    if tama <= n:
        if tama + b >= n:
            break
        tama += b



print(blue)


### FIXED CODE ###

n,a,b = map(int,input().split())
tama = int(n/(a+b))*(a+b)
blue = int(n/(a+b))*a
nokori = n - tama
if nokori<a:
    blue += nokori
else:
    blue += a


print(blue)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,c,d,e,f=LI()

  ans_n=-inf
  ans_pair=[0,0]
  xf=100*e/(100+e)
  for i in range(31):
    for j in range(31):
      for k in range(101):
        for l in range(101):
          xa=100*a*i+100*b*j
          xb=c*k+d*l

          # print(xa,xb)
          if xa+xb>f:
            continue

          if xa+xb==0:
            continue

          xc=100*xb/(xa+xb)
          if xc>xf:
            continue

          if ans_n<xc:
            ans_n=xc
            ans_pair=[xa+xb,xb]

  return str(ans_pair[0])+' '+str(ans_pair[1])

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,c,d,e,f=LI()

  ans_n=-inf
  ans_pair=[0,0]
  xf=100*e/(100+e)
  for i in range(31):
    for j in range(31):
      for k in range(101):
        for l in range(101):
          xa=100*a*i+100*b*j
          xb=c*k+d*l

          # print(xa,xb)
          if xa+xb>f:
            break

          if xa+xb==0:
            continue

          xc=100*xb/(xa+xb)
          if xc>xf:
            continue

          if ans_n<xc:
            ans_n=xc
            ans_pair=[xa+xb,xb]

  return str(ans_pair[0])+' '+str(ans_pair[1])

# main()
print(main())
### BUGGY CODE ###

ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


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


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2

ans %= mod
for i in range(1, bb+1):
    c1 = c1 * (aa + b + i) * inv(b + i)
    c2 = c2 * (bb - i + 1) * inv(a + bb - i)
    ans += c1 * c2
    ans %= mod
print(ans)


### FIXED CODE ###

ai = lambda: list(map(int,input().split()))

mod = 10**9+7


def nCb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod


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


h,w,a,b = ai()
aa = h-a-1
bb = w-b-1
c1 = nCb(aa+b, b)
c2 = nCb(a+bb-1, bb)
ans = c1 * c2
ans %= mod

for i in range(1, bb+1):
    c1 = c1 * (aa + b + i) * inv(b + i) % mod
    c2 = c2 * (bb - i + 1) * inv(a + bb - i) % mod
    ans += c1 * c2
    ans %= mod
print(ans)
### BUGGY CODE ###

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

p2 = int(p ** (1 / n))

for i in range(p2 + 1, 0, -1):
    if p % (i ** n) == 0:
        print(i)
        break

### FIXED CODE ###

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

p2 = round(p ** (1 / n))

for i in range(p2, 0, -1):
    if p % (i ** n) == 0:
        print(i)
        break
### BUGGY CODE ###

from queue import PriorityQueue

n,m,s,t = map(int,input().split())
s-=1
t-=1
edge_a = [[-1]*n for i in range(n)]
edge_b = [[-1]*n for i in range(n)]
for i in range(n):
    edge_a[i][i] = 0
    edge_b[i][i] = 0

for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    edge_a[u][v] = edge_a[v][u] = a
    edge_b[u][v] = edge_b[v][u] = b

def djikstra(s,edges):
    n = len(edges)
    dist = [-1]*n
    visited = {}
    dist[s] = 0
    q = PriorityQueue()
    while len(visited) != n:
        if len(visited) == 0:
            next_p = s
            visited[s] = 0
        else:
            while not q.empty():
                cost, to_ = q.get()
                if to_ not in visited:
                    visited[to_] = cost
                    next_p = to_
                    break

        for to_, cost in enumerate(edges[next_p]):
            if cost >= 0 and to_ not in visited:
                q.put((visited[next_p] + cost, to_))
    return visited

cost_a = djikstra(s,edge_a)
cost_b = djikstra(t, edge_b)

ans = []
for i in range(n)[::-1]:
    nokori = 10**15 - cost_a[i] - cost_b[i]
    if len(ans) == 0:
        ans.append(nokori)
    else:
        ans.append(max(nokori, ans[-1]))
print(*ans[::-1], sep="\n")

### FIXED CODE ###

from heapq import heapify, heappop, heappush
from collections import defaultdict

n,m,s,t = map(int,input().split())
s-=1
t-=1
edge_a = defaultdict(set)
edge_b = defaultdict(set)
for i in range(m):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def djikstra(s,edges):
    n = len(edges)
    visited = {}
    q = []
    while len(visited) != n:
        if len(visited) == 0:
            next_p = s
            visited[s] = 0
        else:
            while q:
                cost, to_ = heappop(q)
                if to_ not in visited:
                    visited[to_] = cost
                    next_p = to_
                    break

        for to_, cost in edges[next_p]:
            if cost >= 0 and to_ not in visited:
                heappush(q, (visited[next_p] + cost, to_))
    return visited

cost_a = djikstra(s,edge_a)
cost_b = djikstra(t, edge_b)

ans = []
for i in range(n)[::-1]:
    nokori = 10**15 - cost_a[i] - cost_b[i]
    if len(ans) == 0:
        ans.append(nokori)
    else:
        ans.append(max(nokori, ans[-1]))
print(*ans[::-1], sep="\n")
### BUGGY CODE ###

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

n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
D = [[-1]*n for _ in range(2)]
def dfs(color, v):
  if D[color][v] != -1:
    return D[color][v]
  l = len(T[v])
  x = X[v]
  dp = [[float("inf")]*(x+1) for _ in range(l+1)]
  dp[0][0] = 0
  for i, nv in enumerate(T[v]):
    for j in range(x+1):
      if j >= X[nv]:
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-X[nv]]+dfs(color, nv))
      if j >= dfs(color^1, nv):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-dfs(color^1, nv)]+X[nv])
  res = min(dp[l])
  D[color][v] = res
  return res
ans = dfs(0, 0)
if ans == float("inf"):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

### FIXED CODE ###

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

n = int(input())
P = list(map(int, input().split()))
T = [[] for _ in range(n)]
for i, p in enumerate(P, 1):
  T[p-1].append(i)
X = list(map(int, input().split()))
D = [[-1]*n for _ in range(2)]
def dfs(color, v):
  if D[color][v] != -1:
    return D[color][v]
  l = len(T[v])
  x = X[v]
  dp = [[float("inf")]*(x+1) for _ in range(l+1)]
  dp[0][0] = 0
  for i, nv in enumerate(T[v]):
    for j in range(x+1):
      if j >= X[nv]:
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-X[nv]]+dfs(color, nv))
      if j >= dfs(color^1, nv):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j-dfs(color^1, nv)]+X[nv])
  res = min(dp[l])
  D[color][v] = res
  return res
ans = dfs(0, 0)
if ans == float("inf"):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")
### BUGGY CODE ###

#データ入力
total = input().rstrip().split(" ")
num_high = int(total[0])
ans = num_high
num_load = int(total[1])
height = input().rstrip().split(" ")
kind_load = []
for i in range(num_load):
    line = input().rstrip().split(" ")
    kind_load.append(line)

#j番目を選ぶ
for j in range(num_high):
    #print(ans)
    choice = j+1
    #J番目の展望台のある道路を探す
    for list in kind_load:
        if str(choice) in list:
            #比較のため、データを取り出す
            choose = list.index(str(choice))
            check_a = int(list[choose])
            if choose == 1:
                check_b =int(list[0])
            else:
                check_b = int(list[1])
            #比較
            if int(height[check_a - 1]) <= int(height[check_b - 1]):
                ans -= 1
                break
print(ans)

### FIXED CODE ###

total = input().rstrip().split(" ")
num_high = int(total[0])
ans = num_high
num_load = int(total[1])
height = input().rstrip().split(" ")
ans = [0 for i in range(num_high)]

for j in range(num_load):
    list = input().rstrip().split(" ")
    check_a = int(list[0])
    check_b = int(list[1])
    if int(height[check_a-1]) <= int(height[check_b-1]):
        ans[check_a-1] = 1
    if int(height[check_b-1]) <= int(height[check_a-1]):
        ans[check_b-1] = 1
print(ans.count(0))
### BUGGY CODE ###

from collections import deque, defaultdict

n, m = list(map(int, input().split()))
a, b = [], []
d = defaultdict(list)
for i in range(m):
    data = list(map(int, input().split()))
    a.append(data[0])
    b.append(data[1])
    d[data[0]].append(data[1])
    d[data[1]].append(data[0])

mindist = defaultdict(lambda: 1000000)
mindist[1] = 0
sign = defaultdict(int)

dq = deque()
dq.append([1, 0])
while len(dq) > 0:
    room, dist = dq.pop()
    for nroom in d[room]:
        if dist + 1 < mindist[nroom]:
            mindist[nroom] = dist + 1
            sign[nroom] = room
            dq.append([nroom, dist + 1])

print('Yes')
for i in range(2, n+1):
    print(sign[i])

### FIXED CODE ###

from collections import deque, defaultdict

n, m = list(map(int, input().split()))
d = defaultdict(list)
for i in range(m):
    data = list(map(int, input().split()))
    d[data[0]].append(data[1])
    d[data[1]].append(data[0])

mindist = defaultdict(lambda: 1000000)
mindist[1] = 0
sign = defaultdict(int)

dq = deque()
dq.append([1, 0])
while len(dq) > 0:
    room, dist = dq.popleft()
    for nroom in d[room]:
        if dist + 1 < mindist[nroom]:
            mindist[nroom] = dist + 1
            sign[nroom] = room
            dq.append([nroom, dist + 1])

print('Yes')
for i in range(2, n+1):
    print(sign[i])
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[False] * 10001 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = True

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i]:
                dp[h+1][w][i+ab] = True
                dp[h+1][w][abs(i-ab)] = True
                dp[h][w+1][i+ab] = True
                dp[h][w+1][abs(i-ab)] = True

for i in range(1000):
    if dp[H][W-1][i]:
        print(i)
        break


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 12801 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(1000):
    if dp[H][W-1][i] == 1:
        print(i)
        break
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = [0]*n
for k in range(n):
    b = a[:]
    del b[k]
    #print(b)
    for l in range(n-2):
        for m in range(l+1, n-1):
            if b[l] == b[m]:
                count[k] += 1

    print(count[k])

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
ans = 0
c = Counter(a)  # aの要素の数と値の辞書を出してくれる
#print(c)
#print(c.keys())
#print(c.values())
for m in c.values():  # Counterで出した辞書の値（values)のリストの中身でfor
    ans += int((m*(m-1))/2)  # mC2をしている


for k in range(n):
    #print(c[a[k]])
    print(ans - (c[a[k]] - 1))
    """
    c[a[k]]-1というのはｋ番目のボールを隠す前と隠した後についての差。
    隠す前、aのリストにA_kがｍ個あったとする。隠した後、aのリストにA_kはｍ－１個
    なので、mC2 - (m-1)C2 = m-1 である。ここでｍとはc[a[k]]なので、上が成り立つ。
    """
### BUGGY CODE ###

import fractions

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

f=fractions.gcd(c,d)
f2=c*d//f


ans = (f2-(f2//c+f2//d-1))*(b//f2)

for i in range(1,b%f2+1):
    if i%c!=0 and i%d!=0:
        ans+=1

ans -= (f2-(f2//c+f2//d-1))*(a//f2)
for i in range(a%f2):
    if i%c!=0 and i%d!=0:
        ans-=1
print(ans)

### FIXED CODE ###

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

f1=fractions.gcd(c,d)
f2=c*d//f1

a=a-1
aa=a-a//c-a//d+a//f2
bb=b-b//c-b//d+b//f2

print(bb-aa)
### BUGGY CODE ###

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

a = []

for i in range(M):
    a.append(int(input()))

    # 隣接してる場合は、0出力で終了
    if a[i] == a[i - 1] + 1:
        print(0)
        exit(0)

dp = [0] * (N + 1)

dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]

print(dp[-1] % 1000000007)




### FIXED CODE ###

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

# a = [int(input()) for _ in range(M)]
a = set([int(input()) for _ in range(M)])

dp = [0] * (N + 1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, N + 1):
    if i in a:
        continue
    else:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= 1000000007

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

import time
N = list(map(int, input().split()))
N2 = [0,0,0]
ans = 0
while True:
    time.sleep(1)
    for i in range(3):
        if  not N[i] %2 == 0:
            print(ans)
            exit()
    N2[0] = (N[1] + N[2]) /2
    N2[1] = (N[0] + N[2]) /2
    N2[2] = (N[0] + N[1]) /2
    #print(N2)
    if N == N2:
        print('-1')
        exit()
    N = N2.copy()
    ans += 1


### FIXED CODE ###

N = list(map(int, input().split()))
N2 = [0,0,0]
ans = 0
while True:
    for i in range(3):
        if  not N[i] %2 == 0:
            print(ans)
            exit()
    N2[0] = (N[1] + N[2]) /2
    N2[1] = (N[0] + N[2]) /2
    N2[2] = (N[0] + N[1]) /2
    #print(N2)
    if N == N2:
        print('-1')
        exit()
    N = N2.copy()
    ans += 1
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val, pc):
    if pc==0:
        return 0
    tmp = val % pc
    if tmp in d:
        return d[tmp] + 1
    npc = 0
    for i in range(tmp.bit_length()):
        if tmp>>i&1:
            npc += 1
    ans = sub(tmp, npc) + 1
    d[val] = ans
    return ans
pc = sum(item=="1" for item in a)
aval = int(a, 2)
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        val = aval - (1<<(n-1-i))
        ans[i] = sub(val, pc-1)
#         print(1, bin(val)[2:], pc-1)
    else:
        val = aval + (1<<(n-1-i))
        ans[i] = sub(val, pc+1)
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = input()
d = {}
def sub(val):
    if val in d:
        return d[val]
    pc = 0
    for i in range(val.bit_length()):
        if val>>i&1:
            pc += 1
    if pc==0:
        ans = 0
    else:
        tmp = val % pc
        if tmp==0:
            ans = 1
        else:
            ans = sub(tmp) + 1
    d[val] = ans
    return ans

pc = sum(item=="1" for item in a)
val0 = 0 # pc-1
val1 = 0 # pc+1
for i in range(n):
    if a[i]=="1":
        if pc>1:
            val0 += pow(2,n-1-i,pc-1)
        val1 += pow(2,n-1-i,pc+1)
        
ans = [None]*n
# print(a)
for i in range(n):
    if a[i]=="1":
        if pc==1:
            val = 0
            ans[i] = 0
        else:
            val = (val0 - pow(2,n-1-i,pc-1))%(pc-1) #(1<<(n-1-i))
            ans[i] = sub(val) + 1
#         print(1, bin(val)[2:], pc-1)
    else:
        val = (val1 + pow(2,n-1-i,pc+1))%(pc+1) #(1<<(n-1-i))
        ans[i] = sub(val) + 1
#         print(0, bin(val)[2:], pc+1)
write("\n".join(map(str, ans)))
### BUGGY CODE ###

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

N = int(input())
words = list()
count = 0
for _ in range(N):
    words.append(sorted(input()))

for i in range(N):
    for j in range(i+1, N):
        if words[i] == words[j]: count += 1

print(count)

### FIXED CODE ###

N = int(input())
words = []
dic = {}
count = 0

for _ in range(N):
    words.append(str(sorted(input())))

for word in words:
    if word in dic:
        count += dic[word]
        dic[word] += 1
    else:
        dic[word] = 1

print(count)
### BUGGY CODE ###

n=int(input())
print(0,flush=True)
la=input()
if la=='Vacant':
  exit()
print(n-1,flush=True)
ra=input()
if ra=='Vacant':
  exit()
l=0
r=n-1
while r>=l+1:
  m=(l+r)//2
  print(m,flush=True)
  s=input()
  if s=='Vacant':
    exit()
  elif (s!=la and (m-l)%2==0) or (s==ra and (m-l)%2==1):
    r=m-1
    ra=s
  else:
    l=m+1
    la=s

### FIXED CODE ###

n=int(input())
def out(t):
  print(t,flush=True)
  s=input()
  if s=='Male':return 0
  elif s=='Female':return 1
  else:exit()
l=0
r=n
f=out(0)
while l+1!=r:
  m=(l+r)//2
  if (m+f)%2==out(m):l=m
  else:r=m
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = []
for _ in range(M):
    xy.append(tuple(map(int, input().split())))
#print(xy)


G = [[] for _ in range(N+1)]
for el in xy:
    x, y = el
    G[x].append(y)
    G[y].append(x)


seen=[False] * (N+1)
def dfs(n):
    seen[n]=True
    group[-1].append(n)
    for child in G[n]:
        if seen[child] == False:
            dfs(child)

group=[]
for i in range(1,N+1):
    if seen[i] == False:
        group.append([])
        dfs(i)
        #print(seen)
#print(seen)
#print(group)

cnt = 0
for el in group:
    temp = set(el) & set([p[i-1] for i in el])
    cnt += len(temp)
print(cnt)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = []
for _ in range(M):
    xy.append(tuple(map(int, input().split())))
#print(xy)


G = [[] for _ in range(N+1)]
for el in xy:
    x, y = el
    G[x].append(y)
    G[y].append(x)


seen=[False] * (N+1)
def dfs(n):
    seen[n]=True
    group[-1].append(n)
    for child in G[n]:
        if seen[child] == False:
            dfs(child)

group=[]
for i in range(1,N+1):
    if seen[i] == False:
        group.append([])
        dfs(i)
        #print(seen)
#print(seen)
#print(group)

cnt = 0
for el in group:
    temp = set(el) & set([p[i-1] for i in el])
    cnt += len(temp)
print(cnt)
### BUGGY CODE ###

# multiple
line = input()
ln = 0
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*10**(i-1))%2019)%2019
    counts[ti1] += 1
    ln = ti1
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))

### FIXED CODE ###

# multiple
line = input()
ln = 0
d = 1
counts=[0]*2019
for i in range(1,len(line) + 1):
    ti1 = (ln +(int(line[-1*i])*d))%2019
    counts[ti1] += 1
    ln = ti1
    d *= 10
    d %= 2019
total = 0
counts[0] +=1
for i in range(len(counts)):
    total += counts[i]*(counts[i] - 1)/2
print(int(total))
### BUGGY CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n+1):
    for j in range(n-i+1):
        k = (n-r*i-j*g)//b
        if sum([r*i,j*g,abs(b*k)]) == n:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(k*b) == n:
            ans += 1
print(ans)
### BUGGY CODE ###

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

for i in range(k):
    if a > 0:
        a -= 1
    elif b > 0:
        b -= 1
    else:
        break
print('{} {}'.format(a, b))

### FIXED CODE ###

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

if k <= a:
    a -= k
elif a < k <= a + b:
    temp = a
    a = 0
    b -= k - temp
else:
    a = 0
    b = 0
print('{} {}'.format(a, b))
### BUGGY CODE ###

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]

for d in dc_list:
    mods = sorted([a % d for a in A])
    if sum(mods) % d != 0:
        continue

    # cs:sumulative sum(累積和)
    mod_cs = [0] * (len(mods) + 1)
    for i, mod in enumerate(mods):
        mod_cs[i + 1] = mod_cs[i] + mod

    for i, mod_cumulative in enumerate(mod_cs):
        minus_op = mod_cumulative
        plus_op = (d * (len(mod_cs) - 1 - i)) - (mod_cs[-1] - mod_cs[i])

        if minus_op == plus_op and minus_op <= K:
            print(d)
            exit(0)
        elif minus_op > K:
            break


### FIXED CODE ###

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
#dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]
dc_list = []
for i in range(1, int(sum_a ** 0.5) + 1):
    if sum_a % i == 0:
        dc_list.append(i)
        if i != sum_a // i:
            dc_list.append(sum_a // i)

dc_list.sort(reverse = True)

for d in dc_list:
    mods = [a % d for a in A]
    mod_sum = sum(mods)
    if mod_sum % d != 0:
        continue
    mods = sorted(mods)

    op = 0
    mod_len = len(mods)
    for i, mod in enumerate(mods):
        op += mod

        if op > K:
            break

        if (mod_len - (i + 1)) * d == mod_sum and op <= K:
            print(d)
            exit(0)