Harryxun/stf_run huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
X = input()
def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt
pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        modm[i] = pow(2, N-1-i, bn-1)

ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sum(modm)
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sum(modp)
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

print(*ans, sep="\n")


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# import random
# N = random.randint(0, 2*100000)
# X = ""
# for i in range(N):
#     if random.random() < 0.5:
#         X += "0"
#     else:
#         X += "1"
# print(N, X)


N = INT()
X = input()

def popcount(n):
    cnt = 0
    while n:
        n %= "{:b}".format(n).count("1")
        cnt += 1
    return cnt

pl = [0]*(N+1)
for i in range(N+1):
    pl[i] = popcount(i)
bn = X.count("1")

modp = [0]*N
modm = [0]*N

for i in range(N):
    if X[i] == "1":
        modp[i] = pow(2, N-1-i, bn+1)
        if not bn == 1:
            modm[i] = pow(2, N-1-i, bn-1)

sp = sum(modp)
sm = sum(modm)
ans = [0]*N
for i in range(N):
    if X[i] == "1":
        if bn == 1:
            ans[i] = 0
            continue
        s = sm
        s -= modm[i]
        s %= bn-1
        ans[i] = pl[s]+1
    else:
        s = sp
        s += pow(2, N-1-i, bn+1)
        s %= bn+1
        ans[i] = pl[s]+1

print(*ans, sep="\n")
from collections import deque
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

que = deque() #座標と距離を保存
que.append((1,1,0)) #スタートの座標と距離を入力

while que:
    i,j,k = que.popleft() #先頭を取得
    for di,dj in move:
        if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
            distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
            que.append((i+di,j+dj,k+1)) #queの末尾に追加

#初期の道のカウント
road = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            road = road + 1

if distance[h-2][w-2] != float('inf'):
    minimum_distance = distance[h-2][w-2]
else:
    minimum_distance = road

print(road - minimum_distance - 1)

### FIXED CODE ###

from collections import deque
#入力
h,w = map(int, input().split())
w = w + 2
maze = [list('#' * (w))]
for i in range(h):
    maze.append(list('#' + input() + '#')) #迷路の読み込み
maze.append(list('#' * (w)))
h = h + 2
                
distance = [[float('inf')] * w for i in range(h)] #まずは無限大の距離と仮定

que = deque() #座標と距離を保存
que.append((1,1,0)) #スタートの座標と距離を入力

move = [(1,0),(-1,0),(0,1),(0,-1)]

while que:
    i,j,k = que.popleft() #先頭を取得
    for di,dj in move:
        if maze[i+di][j+dj] == '.' and distance[i+di][j+dj] > k+1:
            #迷路の道で，今までの距離が今出した距離より長いなら
            distance[i+di][j+dj] = k+1 #より短い今の距離に更新し
            que.append((i+di,j+dj,k+1)) #queの末尾に追加

#初期の道のカウント
road = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            road = road + 1

if distance[h-2][w-2] != float('inf'):
    minimum_distance = distance[h-2][w-2]
else:
    minimum_distance = road

print(road - minimum_distance - 1)
a=list[int(input()) for i in range(5)]
b=int(input())
if a[4]-a[0]>b:
  print('Yay!')
else:
  print(':(')

### FIXED CODE ###

a=[int(input()) for i in range(5)]
b=int(input())
if a[4]-a[0]<=b:
  print('Yay!')
else:
  print(':(')
n=input()
maxn=0
maxccount=0

for i in range(n+1):
  count=0
  while n%2==0:
    n=n/2
    count+=1
  if maxcount < count:
    maxn=i
    maxcount=count

print(maxn)
    

### FIXED CODE ###

n=int(input())
i=1
while i*2<=n:
  i*=2
print(i)
def input_num(infile,outfile):
	num = int(infile.readline())
	return num

def makedict(infile,outfile,n):
	dict = {}
	for i in range(n):
		key,val = infile.readline().split()
		dict[key] = val
	return dict

def replace(infile,outfile,dict,m):
	for i in range(m):
		x = infile.readline().sprit()[0]
		x = dict.get(x,x)
		outfile.write(x)
	print >> outfile

if __name__ == "__main__"
	import sys
	while True:
		n = input_num(sys.stdin,sys.stdout)
		if n == 0:
			break
		dictionary = makedict(infile,outfile,n)
		# dict.update(makedict(infile,outfile,n))
		m = input_num(sys.stdin,sys.stdout)
		replace(infile,outfile,dictionary,m)

### FIXED CODE ###

def convert(infile, outfile, n):
    dictionary = {}
    for i in range(n):
        key, val = infile.readline().split()
        dictionary[key]=val
    m = int(infile.readline())
    for j in range(m):
        x = infile.readline().split()[0]
        outfile.write(dictionary.get(x, x))
    print >> outfile
 
def run(infile, outfile):
    while True:
        n = int(infile.readline())
        if n == 0:
            break
        convert(infile, outfile, n)
 
if __name__ == "__main__":
    import sys
    run(sys.stdin, sys.stdout)
import sys
# s = sys.stdin.readlines()
inputs = sys.stdin.readline()
A = sys.stdin.readline()
inputs = inputs.split()
H, N = inputs[0], inputs[1]
A = A.split()

A_sum = 0
for i in range(len(A)):
    A_sum += A[i]

if A_sum < H:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

import sys
# s = sys.stdin.readlines()
inputs = sys.stdin.readline()
A = sys.stdin.readline()
inputs = inputs.split()
H, N = int(inputs[0]), int(inputs[1])
A = A.split()

A_sum = 0
for i in range(len(A)):
    A_sum += int(A[i])

if A_sum < H:
    print('No')
else:
    print('Yes')
import bisect
N = int(input())
A = [int(i) for i in input().split()]
g = sum(A)/2

S = []
s = 0
for a in A:
    s += a
    S.append(s)

i = bisect.bisect_left(S, g)

if int(g) in S:
    print(0)
else:
    print(min(S[i]-S[i-1], S[i+1]-S[i]))


### FIXED CODE ###

import bisect
import math

N = int(input())
A = [int(i) for i in input().split()]
sa = sum(A)
g = sa/2

S = []
s = 0
for a in A:
    s += a
    S.append(s)


i = bisect.bisect_left(S, g)
print(min(math.ceil(sa-S[i-1]*2), math.ceil(S[i]*2-sa)))
import math
r=int(input())
print("{0:.6f} {1:.6f}".format(r*r*math.pi, 2*r*math.pi))

### FIXED CODE ###

import math
r=float(input())
print("{0:.6f} {1:.6f}".format(r*r*math.pi, 2*r*math.pi))
N =int(input())
#S = list(map(str, input().split()))
# S = list(map(str, input().split()))
S = []
for _ in range(H):
    S.append(input())

#受け取った文字列をアルファベットに並び替え
S=[''.join(sorted(a)) for a in S]

#バケットを作って、出現回数をカウント
count=[0]*(len(set(S)))
unique_S=list(set(S))
ans=0
for ele in S:
    count[unique_S.index(ele)]+=1
count=sorted(count,reverse=True)

#階乗のコード
def cor(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact
#組み合わせのコード
def combination(n,c):
    a=(cor(n))/(cor(n-c)*cor(c))
    return a

for i in count:
    if i==1:
        break
    else:
        ans+=combination(i,2)
print(int(ans))

### FIXED CODE ###

from collections import Counter,defaultdict
N =int(input())
S = []
#キーが存在しなかったときのデフォルトの値を定義できる
dict=defaultdict(int)
ans=0
for _ in range(N):
    s=''.join(sorted(input()))
    ans+=dict[s]
    dict[s]+=1
print(ans)
N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq

lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
right_array = heapq.heapify(array[:N])
left_array = heapq.heapify([-n for n in array[-N:]])
l_sum = sum(left_array)
r_sum = sum(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    right_array.append(new_b)
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))

### FIXED CODE ###

N = int(input())
array = [int(n) for n in input().split()]
import copy
import heapq
lst = [None for i in range(N + 1)]
left_lst = copy.deepcopy(lst)
right_lst = copy.deepcopy(lst)
left_array = array[:N]
right_array= [-n for n in array[-N:]]
l_sum = sum(left_array)
r_sum = sum(right_array)
heapq.heapify(left_array)
heapq.heapify(right_array)
left_lst[0] = l_sum
right_lst[0] = r_sum

for k in range(N, 2 * N):
    new_a, new_b = array[k], array[-k - 1]*-1
    heapq.heappush(left_array,new_a)
    heapq.heappush(right_array,new_b)
    old_a = heapq.heappop(left_array)
    l_sum += (new_a - old_a)
    left_lst[k - N + 1] = l_sum
    old_b = heapq.heappop(right_array)
    r_sum += (new_b - old_b)
    right_lst[k - N + 1] = r_sum
lst = [ a + b for a, b in zip(left_lst, list(reversed(right_lst)))]
print(max(lst))
import math
lists=list(int(input()) for i in range(5))
modlists=list(lists[j]%10 for j in range(5))
a=set(modlists)
if 0 in modlists:
      a.remove(0)
            
#a=list(set(modlists).remove(0) if 0 in modlists else set(modlists))
k=modlists.index(min(a))

b=0
for m in range(5):
      b+=math.ceil(lists[m]/10)*10
print(b-math.ceil(lists[k]/10)*10+lists[k])


### FIXED CODE ###

import math
lists=list(int(input()) for i in range(5))
modlists=list(lists[j]%10 for j in range(5))
x=set(modlists)
if 0 in x :
      x.remove(0)

      
else:
      x=set(modlists)
            
#a=list(set(modlists).remove(0) if 0 in modlists else set(modlists))
k=modlists.index(min(x)) if x else 0


b=0
for m in range(5):
      b+=math.ceil(lists[m]/10)*10
print(b-math.ceil(lists[k]/10)*10+lists[k])
# input
N = int(input())
L = [list(map(int, input().split()))]

ans = 0

for i in range(N):
    ans += L[i][1] - L[i][0] + 1

print(ans)

### FIXED CODE ###

# input
N = int(input())
L = [list(map(int, input().split())) for _ in range(N)]

ans = 0

for i in range(N):
    ans += L[i][1] - L[i][0] + 1

print(ans)
N = int(input())
if N < 105:
  print(0)
elif 105 <= N < 155:
  print(1)
elif 155 <= N < 195:
  print(2)
else:
  print(3)

### FIXED CODE ###

A, B = (int(i) for i in input().split())
C = (A - 1) * (B - 1)
print(C)
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int N, M; cin >> N >> M;
  int XMAX, YMIN; cin >> XMAX >> YMIN;
  for (int i = 0; i < N; ++i) {
    int x; cin >> x;
    XMAX = max(XMAX, x);
  }
  for (int i = 0; i < M; ++i) {
    int y; cin >> y;
    YMIN = min(YMIN, y);
  }
  cout << (XMAX < YMIN ? "No War" : "War") << endl;
}

### FIXED CODE ###

N, M, X, Y = map(int, input().split())
x = max(map(int, input().split()))
y = min(map(int, input().split()))

for z in range(x + 1, y + 1):
    if X < z <= Y:
        print('No War')
        exit()

print('War')
a = int(input())
b = list(map(int, input().split()))
c = 1
for i in b:
    c *= i
if c > 10**18
    print('-1')
print(c)

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

mult = 1

for i in a:
    mult *= i
    if mult > 10**18:
        print(-1)
        exit()
print(mult)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        return self.find[x] == self.find[y]
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)
n = int(input())
s = list(input())

from collections import defaultdict
ans = defaultdict(int)
def dfs(now, pos):
    if len(now) == 3:
        ans[now] = 1
        return
    if pos == n:
        return
    dfs(now+s[pos], pos+1)
    dfs(now, pos+1)

dfs("", 0)

anss = 0
for i in ans.values():
    anss += i

print(anss)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
n = int(input())
s = list(input())

ans = 0
num = [str(i) for i in range(10)]
for i in num:
    for l in range(n):
        if s[l] == i:
            for j in num:
                for m in range(l+1,n):
                    if s[m] == j:
                        for k in num:
                            for p in range(m+1, n):
                                if s[p] == k:
                                    ans += 1
                                    break
                            continue
                        break
            break

print(ans)
n= int(input())
v_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]

for _ in zip(v_list, c_list):
  if(v_list>=c_list):
    val = val + (v_list-c_list)

print(val)

### FIXED CODE ###

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

val = 0
for v, c in zip(v_list, c_list):
  if(v>=c):
    val = val + (v-c)
   
print(val)
n = int(input())
ans = n
for i in range(int(n**0.5),0,-1):
  if n % i == 0:
    j = target // i
    if (i+j-2) < ans:
      ans = i+j-2
print(ans)

### FIXED CODE ###

n=int(input())
ans=n
for i in range(int(n**0.5),0,-1):
    if n%i==0:
        ans=n//i+i-2
        break
print(ans)
n,k = map(int,input().split())
print(min(abs(n%k),k-abs(n%k))

### FIXED CODE ###

n,k = map(int,input().split())
x = n % k
a = min(abs(k-x),n,x)


print(a)
def get_prime(N):
    if N < 2:
        return {1}
    prime = dict()
    prime[1] = 1

    i = 2
    while i*i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N//i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


n, p = [int(i) for i in input().strip().split()]


prims = get_prime(p)

ans = 1

if n == 1:
    print(p)
    quit()

for p, cnt in prims.items():
    if cnt >= n:
        ans *= p

print(ans)

### FIXED CODE ###


def get_prime(N):
    if N < 2:
        return {1:1}
    prime = dict()
    prime[1] = 1

    i = 2
    while i*i <= N:
        while N % i == 0:
            if i in prime.keys():
                prime[i] += 1
            else:
                prime[i] = 1
            N = N//i
        i += 1
    if N != 1:
        prime[N] = 1
    return prime


n, p = [int(i) for i in input().strip().split()]


prims = get_prime(p)

ans = 1


if n == 1:
    print(p)
    quit()

for p, cnt in prims.items():
    _tmp = cnt//n
    ans *= p**(cnt//n)

print(ans)
from math import sqrt
def main():

    x1, y1, x2, y2 = map(float, input())
    print(sqrt((x2-x1)**2 + (y2-y1)**2))

if __name__ == '__main__':
    main()



### FIXED CODE ###

x1, y1, x2, y2 = map(float, input().split())
dist = ((x2-x1)**2 + (y2-y1)**2)**0.5
print("{:.8f}".format(dist))
o

### FIXED CODE ###

X1, Y1, X2, Y2 = map(int, input().split())
X3, Y3 = X2-(Y2-Y1), Y2+(X2-X1)
X4, Y4 = X3-(Y3-Y2), Y3+(X3-X2)
print(X3, Y3, X4, Y4)
#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

checker = [[0 for _ in range(10)] for _ in range(n)]

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    colors[v] = c
    checker[v][d] = 1 #checked
    
    dfs(d-1, v, c) #dが低いやつについて全て埋めておく必要がある。もう先着ありで無理ですよ、って宣言。
    
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

        

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v-1,c)
    
for i in range(n):
    print(colors[i])


### FIXED CODE ###

#b
#上で再起の代わりにナイーブに配列内の値を埋めていく。
#aこのほうがちょい早い。

#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.
#まだ遅い。TLE.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

checker = [[0 for _ in range(11)] for _ in range(n)]        

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    if colors[v]==0: #not colored yet
        colors[v] = c
        
    #ここよ
    for j in range(d+1):
        checker[v][j] = 1
        
        
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v-1,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v,c)
    
for i in range(n):
    print(colors[i])
import Levenshtein

S = list(input())
lenS = len(S)

patternA = []
patternB = []
countA = 0
countB = 0

for x in range(lenS):
    print(S[x])
    if x % 2 == 0:
        if S[x] == "0":
            countA += 1
        else:
            countB += 1
    else:
        if S[x] == "1":
            countA += 1
        else:
            countB += 1

if countA < countB:
    print(countA)
else:
    print(countB)
    

### FIXED CODE ###

S = list(input())
lenS = len(S)

patternA = []
patternB = []
countA = 0
countB = 0

for x in range(lenS):
    if x % 2 == 0:
        if S[x] == "0":
            countA += 1
        else:
            countB += 1
    else:
        if S[x] == "1":
            countA += 1
        else:
            countB += 1

if countA < countB:
    print(countA)
else:
    print(countB)
N=int(input())
A=[]
for n in range(N):
	A.append(input())
B=A.copy()
B.sort()
C=B[N-1]
D=B[N-2]
for i in range(N):
	if A[i]>D:
		print(D)
	else:
		print(C)


### FIXED CODE ###

import copy
N = int(input())
S = []
for i in range(N):
    S.append(int(input()))

B=copy.copy(S)
B.sort()
if N>2:
	C=int(B[N-1])
	D=int(B[N-2])
	for i in S:
		if int(i)>=C:
			print(D)
		else:
			print(C)

else:
	print(S[1])
	print(S[0])
r = int(input().split(" "))
pi = 3.141592653589
print("{0:0.6f} {1:0.6f}".format((r**2)*pi,r*2*pi))

### FIXED CODE ###

import math
r = float(input())
print("{0:.6f} {1:.6f}".format(r**2*math.pi,r*2*math.pi))
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9) + 7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    assert(a==b)
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 1
    
    for i in range(1, n+1):
        for j in range(1, c+1):
            for k in range(j+1):
                dp[i][j] += (dp[i-1][j-k] * pow(a[i-1], k, MOD)) % MOD
    print(dp[n][c])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

MOD = pow(10, 9)+7

def main():
    n, c = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    # 部分点
    # dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    # dp[0][0] = 1
    # for i in range(1, n+1):
    #     for j in range(c+1):
    #         for k in range(j+1):
    #             dp[i][j] += dp[i-1][j-k]*pow(a[i-1], k, MOD)
    #             if dp[i][j] >= MOD:
    #                 dp[i][j] -= MOD
    abc = [[0 for _ in range(401)] for _ in range(401)]
    # abc[i][j]: j**i
    for i in range(401):
        abc[0][i] = 1
    abc[0][0] = 0
    for i in range(1, 401):
        for j in range(1, 401):
            abc[j][i] = abc[j-1][i] * i % MOD
    
    for i in range(1, 401):
        for j in range(401):
            abc[j][i] += abc[j][i-1]
            if abc[j][i] >= MOD:
                abc[j][i] -= MOD
    
    dp = [[0 for _ in range(c+1)] for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(c+1):
            for k in range(j+1):
                accm = abc[k][b[i-1]] - abc[k][a[i-1]-1]
                if accm < 0:
                    accm += MOD
                dp[i][j] += dp[i-1][j-k] * accm % MOD
                if dp[i][j] >= MOD:
                    dp[i][j] -= MOD
    
    print(dp[n][c])


if __name__ == '__main__':
    main()
n,a,b=map(int,input().split())
print(min(a*t,b))

### FIXED CODE ###


n,a,b=map(int,input().split())
print(min(a*n,b))
def sol()
  last=int(input()[-1])
  if last in [2,4,5,7,9]:
    return 'hon'
  if last in [0,1,6,8]:
    return 'pon'
  return 'bon'

sol()

### FIXED CODE ###

def sol():
  last=int(input()[-1])
  if last in [2,4,5,7,9]:
    return 'hon'
  if last in [0,1,6,8]:
    return 'pon'
  return 'bon'

print(sol())
a = int(input())
b = list(int,input().split())
c = 1/b[0]
for i in range(a-1):
  c = c + 1/b[i]
print(1/c)

### FIXED CODE ###

a = int(input())
b = list(map(int,input().split()))
c = 0
for i in range(a):
  c += 1/b[i]
print(1/c)