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

N = int(input())
L = [[] for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0
for i in range(N):
    tmp = format(As[i], 'b').zfill(60)
    for j in range(60):
        L[j].append(int(tmp[j]))

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[-(i+1)]
    a = sum(L[i]) % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)

### FIXED CODE ###

N = int(input())
L = [0 for i in range(60)]
As = list(map(int, input().split()))
mod = 1000000007
ans = 0

for A in As:
    for i in range(60):
        if A >> i & 1 == 1:
            L[i] += 1

acc = 1
tmps = []
for i in range(60):
    tmps.append(acc)
    acc = acc * 2 % mod

for i in range(60):
    tmp = tmps[i]
    a = L[i] % mod
    b = (N - a) % mod
    ans += (tmp * a * b) % mod

ans = ans % mod
print(ans)
### BUGGY CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
b = 10**9+7
ans = 0
for i in range(N-1):
    tmp = A[i+1:]
#    print(tmp)
    ans += A[i]*sum(tmp)
print(ans%b)


### FIXED CODE ###

import functools
import operator

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
ans = 0
v = sum(A)
for i in range(N-1):
    v -= A[i]
    ans += A[i]*v
print(ans%mod)
### BUGGY CODE ###

H ,K = input().split(" ")
H = int(H)
K = int(K)


lst = input().split(" ")
hps = []
for l in lst:
  hps.append(int(l))

hps.sort(reverse=True)

for k in range(K):
  if hps:
  	hps.pop(0)
  else:
    break

if hps:
  sum_hps = sum(hps)
else:
  sum_hps = 0
print(sum_hps)

### FIXED CODE ###

H ,K = input().split(" ")
H = int(H)
K = int(K)


lst = input().split(" ")
hps = []
for l in lst:
  hps.append(int(l))

hps.sort(reverse=True)

if len(hps) < K:
  hps = [0]
else:
  hps = hps[K:]

sum_hps = sum(hps)
print(sum_hps)
### BUGGY CODE ###

S=input()
mod=10**9+7
dp=[[0]*13 for _ in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
  for j in range(13):
    if S[i]=='?':
      for k in range(10):
        a=(10*j+k)%13
        dp[i+1][a]=(dp[i][j]+dp[i+1][a])%mod
    else:
      b=int(S[i])
      a=(10*j+b)%13
      dp[i+1][a]=(dp[i+1][a]+dp[i][j])%mod
print(dp[len(S)][5])

### FIXED CODE ###

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

def Eratosthenes(n):
	N = {i:True for i in range(2,n+1)}
	primeNumbers = []
	for i in range(2,n+1):
		if N[i]:
			primeNumbers.append(i)
			j = i*2
			while j<=n:
				N.update({j:False})
				j += i
	return primeNumbers

while True:
	P = Eratosthenes(999999)
	try:
		n = int(input())
		print(len([x for x in P if x<=n]))
	except EOFError:
		break

### FIXED CODE ###

def Eratosthenes(n):
	N = [1 for i in range(0,n+1)]
	i = 3
	while i*i<=n:
		if N[i]:
			j = i*i
			while j<=n:
				N[j] = 0
				j += i*2
		i += 2
	return N

N = Eratosthenes(999999)
while True:
	try:
		n = int(input())
	except EOFError:
		break
	cnt = 0
	if n>=2:
		cnt = 1
	for i in range(3, n+1, 2):
		cnt += N[i]
	print(cnt)
### BUGGY CODE ###

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




### FIXED CODE ###

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

import collections
N = int(input())
a = list(map(int,input().split()))
a.sort()
array = []
sum = 0
for i in range(len(a)):
    if a[i] not in array:
        array.append(a[i])

for i in range(len(array)):
    if a.count(array[i]) >= array[i]:
        sum += a.count(array[i]) - array[i]
    else:
        sum += a.count(array[i])
print(sum)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
A = a.sort()
array = list(set(a))
array.sort()
sum = 0
n = 0
for i in range(len(array)):
    cnt = 0
    for j in range(n,len(a)):
        if array[i] == a[j]:
            cnt += 1
        else:
            break
    n += cnt
    if cnt >= array[i]:
        sum += cnt - array[i]
    else:
        sum += cnt
print(sum)
### BUGGY CODE ###

count = int(input())
zenbu = []

for x in range(count):
    keihin = str(input())
    flg = False

    if not keihin in zenbu:
        zenbu.append(keihin)
print(len(zenbu))
        

### FIXED CODE ###

count = int(input())
zenbu = set()
 
for x in range(count):
    keihin = input()
    zenbu.add(keihin)
print(len(zenbu))
### BUGGY CODE ###

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

result = 1

if 0 in A:
    print(0)
else:
    for i in A:
        result *=i
    if result > 10**18:
        print(-1)
    else:
        print(result)


### FIXED CODE ###

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

result = 1
if 0 in A:
    print(0)
else:
    for i in A:
        result *=i
        if result > 10**18:
            print(-1)
            break
    if result <= 10**18:
        print(result)
### BUGGY CODE ###

import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


# @lru_cache(size=None)
def slv(S, K):

    if len(S) <= 50:
        d = set([])
        for i in range(len(S)):
            for j in range(i + 1, len(S) + 1):
                d.add(S[i:j])

    # print('-----')

    import bisect
    S_ = [c for c in S]
    # S_.sort()
    idxs = []

    for k in sorted(set(S_)):
        # print('k', k)
        for i in range(len(S)):
            if S[i] == k:
                idxs.append(i)
        d = []

        for i in idxs:
            for j in range(i + 1, len(S) + 1):
                if len(d) > K and d[-1] < S[i:j]:
                    break
                if S[i:j] not in d:
                    bisect.insort(d, S[i:j])
        if len(d) > K:
            break
    # print(d)
    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    print(slv(S, K))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def slv(S, K):
    d = set([])
    for i in range(len(S)):
        for j in range(i + 1, i + 1 + K):
            d.add(S[i:j])

    return sorted(d)[K - 1]


def main():
    S = read_str()
    K = read_int()
    # K = 3
    # S = ''.join([random.choice('abcdefghijklmnopqrstu') for _ in range(5000)])
    print(slv(S, K))


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

N = int(input())
num = list(map(int, input().split()))

tot = 0
num2 = [0]*(N-1)

for i in range(len(num)-1):
  num2[i] = sum(num[1+i:]) % (10**9+7)
  
for i in range(len(num)-1):
  num1 = num[i] % (10**9+7)
  
  tot += num1 * num2[i]
  
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)

### FIXED CODE ###

N = int(input())
num = list(map(int, input().split()))

tot = 0
num2 = [0]*(N-1)
numtot = sum(num)

for i in range(len(num)-1):
  numtot -= num[i]
  num2[i] = numtot % (10**9+7)
  
  num1 = num[i] % (10**9+7)
  
  tot += num1 * num2[i]
  
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**7)

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

def update(v, p):
    for next in tree[v]:
        if next == v:
            continue
        counter[next] += counter[v]
        update(next, v)
    
tree = [[] for _ in range(N)]
counter = [0] * N

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0, -1)
print(" ".join(map(str, counter)))

### FIXED CODE ###

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

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

def update(v, p):
    for next in tree[v]:
        if next == p:
            continue
        counter[next] += counter[v]
        update(next, v)

tree = [[] for _ in range(N)]
counter = [0] * N

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0, -1)
print(" ".join(map(str, counter)))
### BUGGY CODE ###

import sys
read_=sys.stdin.buffer.readline

N=int(read_())
A=input().split()

B=[A[0]]

cnt=0
for a in A[1:]:
    if cnt%2==0:
        B.insert(0,a)
        cnt+=1
        continue
    B.append(a)
    cnt+=1

if N%2==0:
    print(' '.join(B))
else:
    print(' '.join(reversed(B)))

### FIXED CODE ###

import sys
read_=sys.stdin.buffer.readline

N=int(read_())
A=input().split()

if len(A)==1:
    print(A[0])
    exit()

B1=A[::2]
B2=A[1::2]

if N%2==0:
    B2.reverse()
    B2.extend(B1)
    print(' '.join(B2))
else:
    B1.reverse()
    B1.extend(B2)
    print(' '.join(B1))
### BUGGY CODE ###

from collections import deque
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()))

out = deque()

for i in range(X):
    for j in range(Y):
        for k in range(Z):
            out.append(A[i]+B[j]+C[k])
out = list(out)
out.sort(reverse = True)
for i in range(K):
    print(out[i])

### FIXED CODE ###

from collections import deque
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()))

out = deque()
out2 = deque()

for i in range(X):
    for j in range(Y):
        out.append(A[i]+B[j])
out = sorted(out, reverse=True)
del out[K:]
for i in range(len(out)):
    for j in range(Z):
        out2.append(out[i]+C[j])
out2 = sorted(out2, reverse=True)
for i in range(K):
    print(out2[i])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in a:
    if a.count(i)>=2:
        b.append(i)
b=sorted(b,reverse=True)
if len(b)<=1:
    print(0)
elif b.count(b[0])>=4:
    print(b[0]*2)
else:
    b=list(set(b))
    b=sorted(b,reverse=True)
    print(b[0]*b[1])

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
h,w,i=0,0,0
while i<n-1:
    if a[i]==a[i+1]:
        if h==0:
            h=a[i]
            i+=1 #
        else:
            w=a[i]
            break
    i+=1
print(h*w)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans += a[i] * a[j]

print(ans%(10**9+7))


### FIXED CODE ###

import copy
n = int(input())
a = list(map(int,input().split()))
a_2 = copy.copy(a)
a_2.reverse()
sinu = [0] * n
t = 0
for i in range(n):
    t += a_2[i]
    sinu[i] += t
sinu.reverse()

ans = 0
for i in range(n-1):
    #print(a[i],sinu[i+1])
    ans += a[i] * sinu[i+1]

    
print(ans%(10**9+7))
### BUGGY CODE ###

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

L = [N]

for i in range(2, int(N**0.5)+1):
    if L[-1] != N//i:
        L.append(N//i)
        
c = int(N**0.5)+1
if c > N**0.5:
    c -= 1
    L.append(c)
else:
    L.append(c)


L.reverse()
dp1 = [0 for _ in range(c+len(L))]
dp2 = [0 for _ in range(c+len(L))]

for j in range(1, c+1):
    dp1[j] = N//j
for j in range(1, len(L)):
    dp1[j+c] = N//L[j]*(L[j]-L[j-1])

for i in range(2, K):
    if i%2 == 0:
        dp2[-1] = dp1[1]
        for j in range(2, c+len(L)):
            dp2[c+len(L)-j] = dp2[c+len(L)-j+1]+dp1[j]
        for j in range(1, len(L)):
            dp2[j+c] *= (L[j]-L[j-1])
    else:
        dp1[-1] = dp2[1]
        for j in range(2, c+len(L)):
            dp1[c+len(L)-j] = dp1[c+len(L)-j+1]+dp2[j]
        for j in range(1, len(L)):
            dp1[j+c] *= (L[j]-L[j-1])

if K%2 == 0:
    ans = sum(dp1)
else:
    ans = sum(dp2)

print(ans%(10**9+7))

### FIXED CODE ###

from itertools import accumulate

N,K = map(int, input().split())
mod = 10**9+7
sqt = int(N**0.5)
cnt = [N // i-N // (i+1) for i in range(1, N//sqt)] + [1]*sqt
x = cnt
for _ in range(K):
    x = [(i*j)%mod for i, j in zip(accumulate(reversed(x)), cnt)]
    

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

import copy
n = int(input())
a = []
for s in range(n):
    a.append(int(input()))
for t in range(n):
  if a[t] == max(a):
    b = copy.copy(a)
    b[t:t+1] = []
    print(max(b))
  else:
    print(max(a))

### FIXED CODE ###

import copy
n = int(input())
a = []
for s in range(n):
    a.append(int(input()))
m = max(a)
b = sorted(a)
if b[-2] == m:
  for c in range (n):
    print(m)
else:
  for t in range(n):
    if a[t] == m:
      b = copy.copy(a)
      b[t:t+1] = []
      print(max(b))
    else:
      print(m)
### BUGGY CODE ###

s=list(str(input()))
q=int(input())
now = 0
for _ in range(q):
  lis = list(map(str,input().split()))
  if int(lis[0]) == 1:
    now = (now+1)%2
  else:
    if (int(lis[1])+now)%2 == 1:
      s.insert(0,lis[2])
    else:
      s.append(lis[2])
if now ==0:
  for i in range(len(s)):
    print(s[i],end="")
else:
  for i in range(len(s)):
    print(s[-i-1],end="")
    
  


### FIXED CODE ###

s=str(input())
q=int(input())
now = 0
mae,usiro="",""
for _ in range(q):
  lis = list(map(str,input().split()))
  if int(lis[0]) == 1:
    now = (now+1)%2
  else:
    if (int(lis[1])+now)%2 == 1:
      mae = lis[2]+mae
    else:
      usiro= usiro +lis[2]
s = mae+s+usiro
if now ==0:
  print(s)
else:
  print(s[::-1])
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
from itertools import combinations
comb=combinations(L, 3)
cnt=0
for cb in  comb:
    a,b,c=cb[0],cb[1],cb[2]
    if a<b+c and b<a+c and c<a+b:
        cnt+=1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left

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

def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    dp = np.full((k+1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0

    for i in range(n):
        h = H[i]
        dh = d[h]
        dp2 = np.zeros((k+1, l), dtype=np.int64)
        dp2[0] = np.full(l, 10**13, dtype=np.int64)
        dp2[1:, :] = dp[:-1, :]
        temp = np.concatenate([(h-s)[:dh], np.zeros(l-dh, dtype=np.int64)])
        for j in range(k+1):
            dp2[j, dh] = min(dp2[j, dh], min(dp[j, :]+temp))
        dp = dp2
    print(np.min(dp))


main()

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A  =sorted(A)
for i in range(1,N):
  if i in A :
    k = A.count(i)
    print(k)
    A = A[k:N]
  else:
    print(0)
print(0)

### FIXED CODE ###

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

n = int(input())
c = [0]*(n-1)
s = [0]*(n-1)
f = [0]*(n-1)
for _ in range(n-1):
    c[_], s[_], f[_] = map(int,input().split())

anss =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        for k in range(10**8):
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
            else:
                k += 1
    else:
        anss.append(tmp)
else:
    anss += [0]

for ans in anss:
    print(ans)

### FIXED CODE ###

n = int(input())

c, s, f = [], [], []
for _ in range(n-1):
    x,y,z = map(int,input().split())
    c.append(x)
    s.append(y)
    f.append(z)

anss =[]
for i in range(n-1):
    tmp = 0
    for j in range(i, n-1):
        k = 0
        while 1:
            if tmp <= s[j] + f[j] * k:
                tmp = s[j] + f[j] * k + c[j]
                break
            else:
                k += 1
    else:
        anss.append(tmp)
else:
    anss += [0]

for ans in anss:
    print(ans)
### BUGGY CODE ###

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

for i in range(1,N+1):
  if a.count(i) >= (Q-K+1):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

# coding: utf-8
# Your code here!

N, K, Q = map(int,input().split())
L = [0]*N
for i in range(Q):
    a = int(input())
    L[a-1] += 1

for i in range(N):
    if Q - L[i] < K:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

s = str(input())

l = len(s)
for st in ['01', '10']:
    while st in s:
        s = s.replace(st, '')

print(l - len(s))


### FIXED CODE ###

s = str(input())
z = sum([str(x)=='0' for x in s])
o = sum([str(x)=='1' for x in s])
print(2*min(z, o))
### BUGGY CODE ###

N = int(input())
arr = list(map(int, input().split()))
ans_list = [0] * (N)
ans = []
summ = 0
for i in range(N):
    for j in range(N-i+1,N):
        if (j % i) == 0:
            summ += ans_list[j]
    if (summ % 2) != arr[i]:
        ans_list[i] = 1
        ans.append(arr[i])

print(sum(ans))
for i in range(len(ans)):
    print(ans[i],' ', end="")

### FIXED CODE ###

N = int(input())
arr = list(map(int, input().split()))
ans_list = [0] * (N)
ans = []
for i in range(N):
    summ = 0
    j = N - i
    while j < N:
        j = j + N - i
        if j - 1 < N:
            summ += ans_list[j-1]
    if (summ % 2) != arr[N - i - 1]:
        ans_list[N - i - 1] = 1
        ans.append(N - i)

ans.sort()
print(len(ans))
for i in range(len(ans)):
    if i == len(ans)-1:
        print(ans[i])
    else:
        print(ans[i],'', end="")
### BUGGY CODE ###

import numpy as np
MOD = 10 ** 9 + 7

dp = np.zeros(13, dtype = np.int64)
dp[0] = 1

move = np.arange(0,52,4) % 13
ten = np.ones(10, dtype=np.int64)
for s in input():
  dp = dp[move]
  if s == '?':
    dp = np.convolve(dp, ten)
    dp[:9] += dp[13:22]
    dp %= MOD
  else:
    s = int(s)
    dp = np.concatenate([dp[13-s:13],dp[:13-s]])
  dp %= MOD
  
print(dp[5])


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

N, K = map(int,input().split())
hairetu = []
for _ in range(N):
  a, b = map(int,input().split())
  hairetu.extend([a]*b)
print(sorted(hairetu)[K-1])

### FIXED CODE ###

import sys
N, K = map(int,input().split())
hairetu = []
for _ in range(N): hairetu.append(list(map(int,input().split())))
hairetu.sort()
cnt = 0
for i in range(N):
  cnt += hairetu[i][1]
  if K <= cnt:
    print(hairetu[i][0])
    sys.exit()
### BUGGY CODE ###

import itertools
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int, input().split())) for i in range(d)]
s0 = [a * p for a, p, _ in ls]
s1 = [a * p + c for a, p, c in ls]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        if s + s0[i] >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += ls[i][1]
            if count >= res:
                break
            s += s1[i]
            if s >= g:
                break
    res = min(res, count)
print(res)

### FIXED CODE ###

import itertools
import math

d, g = map(int, input().split())
ls = [[100 * (i + 1)] + list(map(int, input().split())) for i in range(d)]
s0 = [a * p for a, p, _ in ls]
s1 = [a * p + c for a, p, c in ls]

res = float('inf')
for indices in itertools.permutations(range(d)):
    count = 0
    s = 0
    for i in indices:
        if s + s0[i] >= g:
            count += math.ceil((g - s) / (100 * (i + 1)))
            break
        else:
            count += ls[i][1]
            if count >= res:
                break
            s += s1[i]
            if s >= g:
                break
    res = min(res, count)
print(res)
### BUGGY CODE ###

# まずDPを使う理由はあるs[i]=t[j]の時 そのs[i],t[j]を追加した時に増える部分列の場合の数は前の部分列の場合の数+1増えるから
# 前の要素を利用するということはDPを疑う

mod = 10**9 + 7
n,m = map(int, input().split())
s = input().split()
t = input().split()

dp = [[0] * (m+1) for i in range(n+1)]
dp[0][0] = 0 # i番目,j番目を追加すると増える場合のかず
S = [[0] * (m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] += (S[i][j] + 1)
            dp[i+1][j+1] %= mod
        else:
            dp[i+1][j+1] = 0
        S[i+1][j+1] = S[i][j+1] + S[i+1][j] + dp[i+1][j+1] - S[i][j]
        S[i+1][j+1] %= mod

ans = 1
for i in range(n+1):
    for j in range(m+1):
        ans += dp[i][j]%mod

print(S[n][m]+1)

### FIXED CODE ###

# まずDPを使う理由はあるs[i]=t[j]の時 そのs[i],t[j]を追加した時に増える部分列の場合の数は前の部分列の場合の数+1増えるから
# 前の要素を利用するということはDPを疑う
import sys
input=sys.stdin.readline

mod = 10**9 + 7
n,m = map(int, input().split())
s = input().split()
t = input().split()

dp = [[0] * (m+1) for i in range(n+1)]
S = [[0] * (m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            dp[i+1][j+1] += (S[i][j] + 1)
            dp[i+1][j+1] %= mod
        else:
            dp[i+1][j+1] = 0 # i番目,j番目を追加すると増える場合の数 iとjが等しくないならば場合の数は増えないから0
        S[i+1][j+1] = S[i][j+1] + S[i+1][j] + dp[i+1][j+1] - S[i][j]
        S[i+1][j+1] %= mod

print(S[n][m]+1)