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

def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


mod = 10**9+7
n, k = map(int, input().split())
ans = combination(2*n-1, n)
for i in range(k+1, n):
    ans -= combination(n, i) * combination(n-1, i)
    ans %= mod
print(ans)


### FIXED CODE ###

def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)


def combination(n, k, mod=10**9+7):
    numer = denom = 1
    for i in range(k):
        numer = (numer * (n-i)) % mod
        denom = (denom * (i+1)) % mod
    return (numer * mod_inverse(denom, mod)) % mod


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

fact = [1] * (n+1)
fact_inv = [1] * (n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = mod_inverse(fact[i])

ans = combination(2*n-1, n)
for i in range(k+1, n):
    ans -= (fact[n] * fact_inv[i] * fact_inv[n-i]) * (fact[n-1] * fact_inv[i] * fact_inv[n-1-i])
    # ans -= combination(n, i) * combination(n-1, i)
    ans %= mod
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
query = []
for i in range(q):
    query.append(list(map(str, input().split())))
i = 0
while i < q:
    if len(query[i]) == 1:
        if i < q - 1:
            if len(query[i + 1]) == 1:
                i += 2
                continue
        s = s[::-1]
        i += 1
    else:
        if int(query[i][1]) == 1:
            s = query[i][2] + s
            i += 1
        else:
            s = s + query[i][2]
            i += 1
print(s)            

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,y,z,k=MI()
A=LI()
B=LI()
C=LI()
lis=[]
for i in range(x):
    for j in range(y):
        lis.append(A[i]+B[j])
lis.sort(reverse=True)
lisan=[]
for i in range(min(k,x*y)):
    for j in range(z):
        lisan.append(lis[i]+C[j])
lisan.sort(reverse=True)
for i in range(k):
    print(lisan[i])

    
        

    
    


### FIXED CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

x,y,z,k=MI()
A=LI()
B=LI()
C=LI()
lis=[]
for i in range(x):
    for j in range(y):
        lis.append(A[i]+B[j])
lis.sort(reverse=True)
lisan=[]
for i in range(min(k,x*y)):
    for j in range(z):
        lisan.append(lis[i]+C[j])
lisan.sort(reverse=True)
for i in range(k):
    print(lisan[i])
### BUGGY CODE ###

N = int(input())

P = [int(x) for x in input().split()]

Q = sorted(P,key=P.index,reverse=True)

cnt = 1
for i in range(1,N):
  if Q[i-1] < min(Q[i:]):
    cnt += 1  

print(cnt) 

### FIXED CODE ###

N = int(input())

P = [int(x) for x in input().split()]

cnt = 1
m = P[0]
for i in P[1:]:
  if i < m:
    m = i
    cnt += 1

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

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

if 0 in a_lst:
    print(0)
    quit()
else:
    res = a_lst[0]
    for a in a_lst[1:]:
        res *= a
    if res > 10 ** 18:
        print(-1)
    else:
        print(res)

### FIXED CODE ###

n = int(input())
a_lst = list(map(int, input().split()))
max_ = 10 ** 18

if 0 in a_lst:
    print(0)
    quit()
else:
    res = a_lst[0]
    for a in a_lst[1:]:
        res *= a
        if res > max_:
            print(-1)
            quit()
    print(res)
### BUGGY CODE ###

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import product, combinations, permutations
from copy import deepcopy
import sys
import numpy as np
sys.setrecursionlimit(4100000)
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = len(A)%K
    prev = None
    L = 0

    for i in range(N-K+1):
        check = A[i:i+K]
        if i==0:
            acc = 1
            for c in check:
                acc *= c
                prev = acc
        else:
            acc = 1
            for c in check:
                acc *= c
            if prev<acc:
                print("Yes")
            else:
                print("No")
            prev = acc

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
ACC = []
ACC.append(0)
sum = 0
for a in A:
    sum += a
    ACC.append(sum)


L = N-K+1
prev = ACC[K] - ACC[0]
for i in range(1, L):
    score = ACC[i+K] - ACC[i] 
    if prev < score:
        print("Yes")
    else:
        print("No")
    prev = score
### BUGGY CODE ###

def main():
    n = int(input())

    s = list(''.join(sorted(input()[:])) for i in range(n))

    count = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                count += 1

    print(count)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())

    count = 0
    found = {}
    for _ in range(n):
        str = ''.join(sorted(input()))
        if str in found:
            count += found[str]
            found[str] += 1
        else:
            found[str] = 1

    print(count)


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

X = int(input())
time = X
for i in range(X+1):
    if i > time: continue
    for j in range(i+1):
        dist = i + sum(range(j))
        if dist == X:  
            time = i
print(time)

### FIXED CODE ###

import math
X = int(input())
n =  math.ceil((math.sqrt(1+8*X) - 1)/2)
ans = n
print(ans)
### BUGGY CODE ###

def resolve():
    '''
    code here
    '''
    import bisect
    N, M = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(M)]

    A_list.sort()

    for i in range(M):
        b, c = queries[i]
        # print(b,c)
        index_c = bisect.bisect_left(A_list, c)
        # print(index_c)

        if index_c >= b:
            big_A = A_list[index_c:]

            A_list = A_list[b:index_c] + [c]*b + big_A
        else:
            A_list = [c]*index_c + A_list[index_c:]

    # print(A_list)
    print(sum(A_list))




if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    '''
    code here
    '''
    import bisect
    import collections
    N, M = [int(item) for item in input().split()]
    A_list = [int(item) for item in input().split()]
    queries = [[int(item) for item in input().split()] for _ in range(M)]
    queries = sorted(queries, key=lambda x:x[1], reverse=True)
    A_list.sort()

    cnt_b = 0
    D = collections.deque()
    for i in range(M):
        b, c = queries[i]
        cnt_b += b
        for _ in range(b):
            D.append(c)
        if cnt_b >= N:
            break
    D_len = len(D)
    res = 0
    for i in range(N):
        if i < D_len:
            res += max(D[i], A_list[i])
        else:
            res += A_list[i]

    # print(A_list)
    print(res)




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

from collections import Counter
N, X, Y = map(int, input().split())

def dijkstra(s, n, w, cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True
        for j in range(n):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d

cost = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[X-1][Y-1] = 1
cost[Y-1][X-1] = 1

res = Counter()
for i in range(N):
    res += Counter(dijkstra(i, N, N, cost)[:i])

for i in range(N-1):
    print(res[i+1])

### FIXED CODE ###

from collections import Counter, defaultdict, deque

N, X, Y = map(int, input().split())

d = defaultdict(set)
for i in range(N-1):
    d[i].add(i+1)
    d[i+1].add(i)
d[X-1].add(Y-1)
d[Y-1].add(X-1)


cost = [[N]*N for _ in range(N)]

q = deque()

for i in range(N):
    q.append((i, 0))
    cost[i][i] = 0

    while q:
        u, st = q.popleft()

        for v in d[u]:
            if v != u and cost[i][v] > st+1:
                cost[i][v] = st+1
                q.append((v, st+1))

res = Counter()
for i, c in enumerate(cost):
    res += Counter(c[:i])

for i in range(N - 1):
    print(res[i + 1])
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
se=set(A)
ans=0
for el in se:
  if A.count(el)%2==1:
    ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
i=0
ans=0
while i<N:
  p=A[i]
  count=0
  for j in range(i,N):
    if A[j]==A[i]:
      count+=1
    else:
      break
  if count%2==1: ans+=1
  i+=count
print(ans)
### BUGGY CODE ###

import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, K = MI()
    p = LI()
    max_ans = 0
    max_i = 0
    ans = 0

    for i in range(0, N-K+1):
        sum_i = p[i]
        #print("i",i)
        for j in range(i+1,i+K):
            sum_i += p[j]
        #print("sum",sum_i)
        if max_ans <= sum_i:
            max_ans = sum_i
            max_i = i
    #print("max",max_i) 
    for j in range(max_i,max_i+K):
        #print("max_i",j)  
        ans += sum(range(1, p[j] + 1))/p[j]
    
    print(ans)




if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    N, K = MI()
    p = LI()

    sum_i = sum(p[0:K])
    max_ans = sum_i
    max_i = 0
    ans = 0
    for i in range(1, N-K+1):
        sum_i = sum_i - p[i-1] + p[K+i-1]
        #print(i,p[i-1],p[K+i-1])
        #print(sum_i)
        #for j in range(i+1,i+K):
        #    sum_i += p[j]
        #print("sum",sum_i)
        if max_ans <= sum_i:
            max_ans = sum_i
            max_i = i
    #print("max",max_i) 
    for j in range(max_i,max_i+K):
        #print("max_i",j)  
        ans += sum(range(1, p[j] + 1))/p[j]
    
    print(ans)




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

from collections import defaultdict

def dfs(cur_node, candidates, visited, level, cnt):

  while len(candidates) > 0:
    node, level = candidates.pop(0)

    if visited[node]: continue
    visited[node] = True

    if level > 0: cnt += 1

    for n in adj_list[node][FRIEND]:
      if n in adj_list[cur_node][BLOCK]:
        candidates.append((n, 0))
      if visited[n] == False:
        candidates.append((n, level+1))

  return cnt

# -----------------------------------------

FRIEND, BLOCK = 0, 1

N, F, B = list(map(int, input().split()))
adj_list = defaultdict(dict)
for i in range(1, N+1):
  adj_list[i][0] = set()
  adj_list[i][1] = set()

for _ in range(F):
  u, v = list(map(int, input().split()))
  adj_list[u][FRIEND].add(v)
  adj_list[v][FRIEND].add(u)

for _ in range(B):
  u, v = list(map(int, input().split()))
  adj_list[u][BLOCK].add(v)
  adj_list[v][BLOCK].add(u)

ans = []

for i in range(1, N+1):
  visited = [False] * (N+1)
  visited[i] = True
  candidates = []
  for node in adj_list[i][FRIEND]:
    # if status == FRIEND:
    # node, level
    candidates.append((node, 0))

  cnt = 0
  cnt = dfs(i, candidates, visited, 0, 0)
  ans.append(cnt)

print(*ans)

### FIXED CODE ###

class UF():
  def __init__(self, N):
    self.par = [-1] * N

  def union(self, x, y):
    p1,p2 = self.find(x), self.find(y)
    if p1 == p2: return

    if self.par[p1] > self.par[p2]:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

  def find(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]

  def size(self, x):
    return -self.par[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

N,M,K = map(int,input().split())
uf = UF(N)
adj = [ [] for _ in range(N)]
for _ in range(M):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  adj[u].append(v)
  adj[v].append(u)
  uf.union(u,v)

res = []
for n in range(N):
  res.append(uf.size(n) - 1 - len(adj[n]))

for _ in range(K):
  u,v = map(int,input().split())
  u -= 1
  v -= 1
  if uf.same(u,v):
    res[u] -= 1
    res[v] -= 1

print(" ".join(map(str, res)))
### BUGGY CODE ###

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

def f(p):
    #(p*(p+1)/2)/p
    return (p+1)/2


p2 = []

for p_tmp in p:
    p2.append(f(p_tmp))

def func1():
    ans = -1000
    tmp = 0
    for i in range(n):
        if(i<k):
            tmp = tmp + p2[i]
        else:
            tmp = tmp - p2[i-k] + p2[i]
            ans = max(ans,tmp)
    return ans

def func2():
    ans = 0
    for i in range(n):
        tmp = 0
        for j in range(k):
            if(i+j >= len(p2)):
                continue
            tmp = tmp + p2[i+j]
        ans = max(ans,tmp)
    return ans

#print('{:.10f}'.format(func1()))
print('{:.10f}'.format(func2()))

### FIXED CODE ###

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

def f(p):
    #(p*(p+1)/2)/p
    return (p+1)/2


p2 = []

for p_tmp in p:
    p2.append(f(p_tmp))

p3 = [p2[0]]

for i in range(1,len(p2)):
    p3.append(p2[i]+p3[i-1])

ans = p3[k-1]
for i in range(k,n):
    ans = max(ans,p3[i]-p3[i-k])

print('{:.20f}'.format(ans))
### BUGGY CODE ###

import copy
import numpy as np
from scipy.sparse import csr_matrix

def openinput() :
    n, m = map(int, input().split())
    s ,t = [], []
    for _ in range(m):
        si, ti = map(int, input().split())
        s.append(si - 1)
        t.append(ti - 1)
    return n, m, s, t

def make_adjacency_matrix(weights, edges, num_of_nodes):
    return csr_matrix((weights, edges), shape=(num_of_nodes, num_of_nodes)).toarray()

def next_nodes(adjacency_matrix, node):
    return [v for (v, e) in enumerate(adjacency_matrix[node]) if e > 0]


def to_n_expected(adjacency_matrix, num_of_nodes, recursive_depth=0):
    dp_table = np.zeros(num_of_nodes)

    recursive_expected = []
    for v in range(num_of_nodes-1, 0, -1):
        nexts = next_nodes(adjacency_matrix, v-1)
        if recursive_depth < 1:
            max_next = nexts[np.argmax(dp_table[next] for next in nexts)]
            adjacency_matrix[v-1, max_next] = 0
            expected = to_n_expected(adjacency_matrix, num_of_nodes, recursive_depth=1)
            adjacency_matrix[v-1, max_next] = 1
            recursive_expected.append(expected)
        
        num_of_nexts = len(nexts)
        if num_of_nexts > 0:
            dp_table[v-1] = 1 + sum(dp_table[next] for next in nexts) / num_of_nexts
        else:
            dp_table[v-1] = np.inf
    recursive_expected.append(dp_table[0])
    return min(recursive_expected)

if __name__ == '__main__':
    n, m, s, t = openinput()
    adjacency_matrix = make_adjacency_matrix([1]*m, (s,t), n)
    expcted_values = to_n_expected(adjacency_matrix, n)
    print(expcted_values)

### FIXED CODE ###

# reference: https://www.onakasuitacity.com/abc144-f/

import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   # O(m)
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      # O(m)
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      # O(m)
    outgoing_degree = len(outgoing[v])
    if outgoing_degree <= 1:
        continue

    max_post = max(posts, key= lambda pos: ex_dp[pos])
    diff_v_ex = 0
    for w in posts:
        if w == max_post:
            diff_v_ex -= 1/outgoing_degree * ex_dp[w]
        else:
            diff_v_ex += 1/(outgoing_degree*(outgoing_degree-1)) * ex_dp[w]
    min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)
### BUGGY CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
PQ = [ [int(j) for j in input().split()] for _ in range(K)]
RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = PQ[i]
    UF1.unite(p,q)
for i in range(L):
    p,q = RS[i]
    UF2.unite(p, q)
counter=[]
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
from collections import Counter  
p=Counter(counter)

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = p[UF1.find(i)+UF2.find(i)*10**6]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))


### FIXED CODE ###

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


class UFT:
    def __init__(self, N):
        self.UFdata = [-1] * (N+1)
        self.rank   = [0]  * (N+1)

    def find(self,x):
        UFdata = self.UFdata
        while UFdata[x] != -1:
            x = UFdata[x]
        return x

    def unite(self,x,y):
        UFdata = self.UFdata
        rank = self.rank 
        find = self.find

        x = find(x)
        y = find(y)
        if x != y:
            if rank[x] < rank[y]:
                x,y = y,x
            if rank[x] == rank[y]:
                rank[x] += 1
            UFdata[y] = x       
            

UF1 = UFT(N)
UF2 = UFT(N)
ans = [1] * (N+1)
# MAP= [ [0] * (N+1) for _ in range(N+1)]
import sys
input = sys.stdin.readline
#PQ = [ [int(j) for j in input().split()] for _ in range(K)]
#RS = [ [int(j) for j in input().split()] for _ in range(L)]

for i in range(K):
    p,q = map(int,input().split())
    UF1.unite(p,q)
for i in range(L):
    p,q = map(int,input().split())#RS[i]
    UF2.unite(p, q)
counter=[]
from collections import defaultdict
cntdic =defaultdict(int)
for i in range(1,N+1):
  counter.append(UF1.find(i)+UF2.find(i)*10**6)
  cntdic[counter[-1]]+=1 

ans = [0]*(N+1)
for i in range(1,N+1):
    ans[i] = cntdic[counter[i-1]]

del ans[0]
# print(" ".join( map(lambda x: str(x), connected_num[1:])))
print(" ".join( map(lambda x: str(x), ans)))
### BUGGY CODE ###

N, M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

MOD = 10**9 + 7

# dp[i+1][j+1] : S_iまで，T_jまでで作ることのできる共通部分列の数
dp = [[0] * 2010 for _ in range(2010)]
dp[0][0] = 1

for i in range(N+1):
    for j in range(M+1):
        if i > 0: dp[i][j] += dp[i-1][j]
        if j > 0: dp[i][j] += dp[i][j-1]
        if i > 0 and j > 0:
            dp[i][j] -= dp[i-1][j-1]
            if S[i-1] == T[j-1]: dp[i][j] += dp[i-1][j-1]
        dp[i][j] = (dp[i][j] + MOD) % MOD

print(dp[N][M])

### FIXED CODE ###

N, M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

MOD = 10**9 + 7

# dp[i+1][j+1] : S_iまで，T_jまでで作ることのできる共通部分列の数
dp = [[0] * 2010 for _ in range(2010)]
dp[0][0] = 1

for i in range(N+1):
    for j in range(M+1):
        if i > 0: dp[i][j] += dp[i-1][j]
        if j > 0: dp[i][j] += dp[i][j-1]
        if i > 0 and j > 0:
            dp[i][j] -= dp[i-1][j-1]
            if S[i-1] == T[j-1]: dp[i][j] += dp[i-1][j-1]
        dp[i][j] = (dp[i][j] + MOD) % MOD

print(dp[N][M])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    # input
    N,W = map(int,input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]==float("inf"):
            pass
        elif dp[-1][i]<=W:
            ans = i
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    # input
    N,W = map(int,input().split())
    w,v = [0]*N,[0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    
    # init dp
    v_max = sum(v)
    dp = [[float("inf") for i in range(v_max+1)] for _ in range(N)]
    dp[0][v[0]] = w[0]
    for i in range(N):
        dp[i][0] = 0

    for i in range(1,N):
        for j in range(v_max+1):
            if j<v[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
    ans = 0
    for i in range(v_max+1):
        if dp[-1][i]<=W:
            ans = i
        else:
            pass
    print(ans)
if __name__ == "__main__":
    main()