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

from itertools import product

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for d in range(N):
    if S[d] == '?':
        for i, j in product(range(13), range(10)): # '?' = j
            rem = ((10 * i) % 13 + j) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
    else:
        for i in range(13):
            rem = ((10 * i) % 13 + int(S[d])) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
print(dp[N][5])

### FIXED CODE ###

from itertools import product

MOD = 10**9 + 7
S = input()
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for d in range(N):
    if S[d] == '?':
        for i, j in product(range(13), range(10)): # '?' = j
            rem = ((10 * i) % 13 + j) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
    else:
        for i in range(13):
            rem = ((10 * i) % 13 + int(S[d])) % 13
            dp[d + 1][rem] += dp[d][i]
            dp[d + 1][rem] %= MOD
print(dp[N][5])
### BUGGY CODE ###

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

mod = 10**9+7

n = int(input())
a = [int(i) for i in input().split()]


factorial = [1]

for i in range(1,n+2):
    tmp = factorial[-1]*i
    factorial.append(tmp)

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]//(factorial[n-r]*factorial[r])

A = copy.deepcopy(a)
A.sort()
for i in range(n+1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    # print(n+1,k,l+n-r,k-1)
    ans = (combinations_count(n+1,k)-combinations_count((l+n-r),(k-1)))%mod
    print(ans)


### FIXED CODE ###

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

mod = 10**9+7



n = int(input())
a = [int(i) for i in input().split()]


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

A = copy.deepcopy(a)
A.sort()
for i in range(n+1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    # print(n+1,k,l+n-r,k-1)
    ans = (combinations_count(n+1,k)-combinations_count((l+n-r),(k-1)))%mod
    print(ans)
### BUGGY CODE ###

from collections import Counter
import bisect

def sortedexist(list,x):
    if bisect.bisect_left == bisect.bisect_right:
        return False
    else:
        return True

N = int(input())
A = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
done = dict()
for a in A:
    done[a] = False
dp = [False] * (max(A) + 1)

for a in A:
    if done[a]:
        dp[a] = True
    else:
        for j in range(2,1 + (max(A) // a)):

            dp[a*j] = True
        done[a] = True
print(sum([dp[a] == False for a in A ]))

### FIXED CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)
### BUGGY CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        A[i] = A[i][:j] + '.' + A[i][j + 1:]
        break
visited = [[False] * W for _ in range(H)]
ans = min([i, H - 1 - i, j, W - 1 - j])
Q = collections.deque([[i, j, K]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.':
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res]]
            Q += [[h + 1, w, res]]
            Q += [[h, w - 1, res]]
            Q += [[h, w + 1, res]]
print(1 + math.ceil(ans / K))


### FIXED CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h in range(H):
    if 'S' in A[h]:
        w = A[h].index('S')
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))
### BUGGY CODE ###

n = int(input())
height = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if(j-i == height[j] + height[i]):
            ans += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict

n = int(input())
height = list(map(int, input().split()))
ans = 0

d = defaultdict(int)

for i in range(n):
    x = i+height[i]
    d[x] += 1

for i in range(n):
    x = i-height[i]
    ans += d[x]

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

n = int(input())
a = [int(input()) for i in range(n)]
sum_a = sum(a)
for i in range(n):
    tmp = a[i]
    a[i] = 0
    print(max(a))
    a[i] = tmp


### FIXED CODE ###

import itertools

n = int(input())
a = [int(input()) for i in range(n)]

max_list = [0] + list(itertools.accumulate(a, func=max))
max_list_r = ([0] +list(itertools.accumulate(reversed(a), func=max)))[::-1]
for i in range(n):
    print(max(max_list[i], max_list_r[i + 1]))
### BUGGY CODE ###

from fractions import gcd

def lcm(a):
    ans = a[0]
    for i in range(1,len(a)):
        ans = (ans//gcd(ans,a[i]))*a[i]
    return ans

N = int(input())
A = tuple(map(int,input().split(" ")))
g = lcm(A)
ans = 0
for i in A:
    ans += g//i
    ans %= (10**9+7)

print(ans)

### FIXED CODE ###

def gcd(a,b):
    while b:a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)

N = int(input())
A = tuple(map(int,input().split(" ")))
ans = 0
mod = 10**9+7
l = 1
for i in range(N):
    l = lcm(l,A[i])
l %= mod

for i in A:
    ans += l*pow(i,mod-2,mod)
    ans %= mod

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

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

for x in range(1,n+1):
    for y in range(n):
        if x == a[y]:
            print(y+1, end=" ")

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)
h = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    h[p] += x


def down_tree(index, parent):
    global score
    score[index] += score[parent] + h[index]
    for i in to[index]:
        if i == parent:
            continue
        down_tree(i, index)
    return


down_tree(1, 1)

print(' '.join(map(str, score[1:])))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
### BUGGY CODE ###

def classify(a,b,c,T):
    if T[a][1]!=T[b][1] and T[b][1]!=T[c][1] and T[c][1]!=T[a][1]:
        return 1
    else:
        return 0
X,Y,Z,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
XY=[]
for a in A:
    for b in B:
        XY.append(a+b)
XY.sort(reverse=True)
XY=XY[:K]
XYZ=[]
for xy in XY:
    for c in C:
        XYZ.append(xy+c)
XYZ.sort(reverse=True)
for xyz in XYZ[:K]:
    print(xyz)


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
    
    if count > k :
        result = False
    else:
        result = True

    return result


def pout(k,w,maxP):
    count = 1
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
    
    if count > k :
        result = False
    else:
        result = True

    return result, count, mP


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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = 10000*100000
rangeMin = 1

while _:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == False and p(k,w,rangeMid+1) == False:
        rangeMin = rangeMid
    elif p(k,w,rangeMid) == True and p(k,w,rangeMid+1) == True:
        rangeMax = rangeMid
    else:
        break

print(pout(k,w,rangeMid+1)[2])

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

N = int(input())
nu = [int(x) for x in input().split()]
r2 = {}

for i in nu:
  r2[i] = nu.index(i)

j2 = []
for i in range(len(r2)):
  j2.append(r2[i+1]+1)
#print(j2)

answ = ""
for i in j2:
  answ += str(i) + " "
print(answ)


### FIXED CODE ###

from sys import stdin
import numpy as np


# noinspection PyShadowingBuiltinsInspection

def main():
    n = int(input())
    students = [int(x) for x in input().split()]
    ret = [0] * n
    for i in range(n):
        ret[students[i] - 1] = i + 1
    print(" ".join([str(x) for x in ret]))
    return


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

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

a.sort()

for i in range(m):
  a[-1] = int(a[-1] / 2)
  a.sort()
    
print(sum(a))

### FIXED CODE ###

import heapq

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

def minus_int(x):
  return -1 * int(x)

a = list(map(minus_int, input().split()))
heapq.heapify(a)

for i in range(m):
  maxp = heapq.heappop(a)
  maxp = -int(-maxp // 2)
  heapq.heappush(a, maxp)
  
print(-sum(a))
### BUGGY CODE ###

N, K = map(int, input().split())
l = []
for _ in range(N):
    an, bn = map(int, input().split())
    for _ in range(bn):
        l.append(an)
l.sort()
print(l[K-1])

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
a_list = []
b_list = []
for i in range(N):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

a_order = np.argsort(a_list)
kc = 0
for i in range(N):
    kc += b_list[a_order[i]]
    if kc >= K:
        print(a_list[a_order[i]])
        break
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        for k in range(j + 1, n):
            c = L[k]
            if a < b + c and b < c + a and c < a + b:
                ans += 1
print(ans)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        k = bisect.bisect_left(L[j + 1:], a + b)
        ans += k
print(ans)
### BUGGY CODE ###

#ABC162c
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
abc = 0

for i in range(1,k+1):
    for i2 in range(1,k+1):
        ab = gcd(i,i2)
        for i3 in range(1,k+1):
            abc += gcd(ab, i3)
print(abc)


### FIXED CODE ###

#ABC162c
from math import gcd
K = int(input())+1
Sum = 0
for i in range(1,K):
    for j in range(1,K):
        d = gcd(i,j)
        for k in range(1,K):
            Sum+=gcd(d,k)

print(Sum)
### BUGGY CODE ###

n, m = map(int, input().split())
g = [0] * n
for i in range(m):
    l, r = map(int, input().split())
    for j in range(l-1, r):
        g[j] += 1
ans = 0
for i in range(n):
    if g[i] == m:
        ans += 1
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = 1
b = n
for i in range(m):
    l, r = map(int, input().split())
    if a < l:
        a = l
    if b > r:
        b = r
if a > b:
    print(0)
else:
    print(b - a + 1)
### BUGGY CODE ###

def main():
    votes = int(input());
    ratio = [[ int(i) for i in input().split() ] for j in range(votes)]

    tak = aok = 0
    for i in range(votes):
        takTemp,  aokTemp = ratio[i][0], ratio[i][1]

        while tak > takTemp or aok > aokTemp:
            takTemp += ratio[i][0]
            aokTemp += ratio[i][1]

        tak, aok = takTemp, aokTemp

        #print("turn:" + str(i))
        #print("votes:" + str(ratio[i][0]) + ":" + str(ratio[i][1]) )
    print(tak + aok)

if __name__ == '__main__':
  main()


### FIXED CODE ###

import math
from decimal import *

def main():
    votes = int(input())
    ratio = [[ int(i) for i in input().split() ] for j in range(votes)]

    votesTemp = [0, 0]
    for i in range(votes):
        if i == 0:
            votesTemp = ratio[i]
            continue

        ceil = [ math.ceil(Decimal(votesTemp[j]) / Decimal(ratio[i][j])) for j in range(2)]

        votesTemp = [ max(ceil) * ratio[i][j] for j in range(2) ]

        """
        print("turn: " + str(i))
        print("votes: " + str(ratio[i][0]) + ":" + str(ratio[i][1]) )
        print("Temp: " +str(votesTemp[0])+":"+str(votesTemp[1]))
        """
    print(sum(votesTemp))

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

s=input()

n=int(input())

ans = []

for i in range(len(s)+1):
    for j in range(i):
        if s[j:i] not in ans:
            ans.append(s[j:i])
ans.sort()
print(ans[n-1])

### FIXED CODE ###

s=input()
 
n=int(input())
 
ans = []
 
for i in range(len(s)):
    for j in range(1,7):
        if s[i:i+j] not in ans and j <= len(s):
            ans.append(s[i:i+j])
ans.sort()
#print(ans)
print(ans[n-1])
### BUGGY CODE ###

n, m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]

for i in range(m):
    b, c = [int(_) for _ in input().split()]
    a.extend([c for _ in range(b)])

a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n, m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
a.sort(reverse=True)

s = []
for i in range(m):
    s.append([int(_) for _ in input().split()])
s.append([0,0])
s.sort(reverse=True, key=lambda x:x[1])

ida = 0
ids = 0
ans = 0
cnt = 0
while cnt < n:
    if a[ida] >= s[ids][1]:
        ans += a[ida]
        ida += 1
        cnt += 1
    else:
        an = min(n - cnt, s[ids][0])
        ans += s[ids][1] * an
        ids += 1
        cnt += an
print(ans)
### BUGGY CODE ###

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  for j in range(b,r+1):
    if Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    dic[Cs[j]] = j
    bt.add(j, 1)
  ans[i] = bt.get(l-1,r)
  b = r + 1
  
for i in range(Q):
  print(ans[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = input()

c = set()

for sc in combinations(s, 3):
    c.add(sc)

print(len(c))



### FIXED CODE ###

from itertools import product

n = int(input())
s = input()

ans = 0

for cmb in product(range(10), range(10), range(10)):
    idx = -1
    for i in cmb:
        idx = s.find(str(i), idx + 1)
        if idx < 0:
            break
    else:
        ans += 1

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

import numpy as np

n, k, q = map(int, input().split())

arr = np.array([k] * n)

for i in range(q):
    q_i = int(input())
    arr = arr - 1
    arr[q_i - 1] += 1


arr_evaluate = arr > 0

for go_or_not in arr_evaluate:
    if go_or_not:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

n, k, q = map(int, input().split())
q_list = [int(input()) for i in range(q)]

arr = [k - q] * n

for q_i in q_list:
    arr[q_i - 1] += 1

for go_or_not in arr:
    if go_or_not > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def calc():
    n = int(input())
    a = [int(x) for x in input().split()]
    k = [0] * n
    cnt = 0
    for i in range(n):
        for j in range(i):
            if i == j:
                continue
            if k[i] == 0 and a[i] % a[j] == 0:
                cnt += 1
                k[i] = 1
            if k[j] == 0 and a[j] % a[i] == 0:
                cnt += 1
                k[j] = 1
    print(n - cnt)

calc()

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)
### BUGGY CODE ###

import itertools

N = int(input())
s = [input() for i in range(N)]

for i, s_i in enumerate(s):
    s_l = list(s_i)
    s_l.sort()
    a = ""
    for c in s_l:
        a += c
    s[i] = a

cnt = 0
count_dict = {}
for j in range(N):
    count_dict[s[j]] = 0
for k in range(N):
    count_dict[s[k]] += 1

for v in count_dict.values():
    cnt += len(list(itertools.combinations(range(v), 2)))

print(cnt)

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


N = int(input())
s = [input() for i in range(N)]

for i, s_i in enumerate(s):
    s_l = list(s_i)
    s_l.sort()
    a = ""
    for c in s_l:
        a += c
    s[i] = a

cnt = 0
count_dict = {}
for j in range(N):
    count_dict[s[j]] = 0
for k in range(N):
    count_dict[s[k]] += 1

for v in count_dict.values():
    if v >= 2:
        # cnt += int(factorial(v)) / int(factorial(2)) / int(factorial(v - 2))
        cnt += cmb(v, 2)

print(cnt)
### BUGGY CODE ###

n=int(input())
s=[input()for _ in range(n)]
ls,w,word=[],[],[]

for i in s:
  w.append(i)
  if i in w:
    ls.append(w.count(i))
    
  else:
    ls.append(1)

for i in range(n):
  if ls[i]==max(ls):
    word.append(w[i])
    
if set(word)==1:
  print(word[0])
  
else:
  word=sorted(set(word))
  for i in range(len(word)):
    print(word[i])

### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
s.sort()
ans,be=[],""
cnt,maxcount=1,0

for i in range(n):
  if be==s[i]:
    cnt+=1
    
  else:
    if cnt>=1:
      if cnt>maxcount:
        maxcount=cnt
        ans.clear()
        ans.append(be)
      
      elif cnt==maxcount:
        ans.append(be)
      
      cnt=1
  be=s[i]
  if i==n-1:
    if cnt>=1:
      if cnt>maxcount:
        maxcount=cnt
        ans.clear()
        ans.append(be)
      
      elif cnt==maxcount:
        ans.append(be)
    
ans.sort()
for i in ans:
  if i!="":
    print(i)
### BUGGY CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
j = 1
for k in range(60):
  s = [A[i][59-k] for i in range(N)]
  v = s.count('0')*s.count('1')
  S += (v * j) % mod
  j *= 2
  j %= mod
  S %= mod
S %= mod
print(S)

### FIXED CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [b[59-k] for b in A]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)
### BUGGY CODE ###

import sys

n, k = map(int, sys.stdin.readline().split())

dp = [[0 for i in range(k+1)] for j in range(n+1)]


for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    
    for j in range(0, k+1):
        if j >= w:
            dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
            
print(max(dp[-1]))

### FIXED CODE ###

import sys
import numpy as np

n, k = map(int, sys.stdin.readline().split())

dp = np.zeros((n+1, k+1))

for i in range(1,n+1):
    w, v = map(int, sys.stdin.readline().split())
    dp[i] = dp[i-1]
    dp[i][w:] = np.maximum(dp[i-1][:-w]+v, dp[i-1][w:])

print(int(np.max(dp[n])))