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

import sys

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = [0 for i in range(maxA+1)]
    for a in A:
        cntA[a] += 1

    ans = 0
    ones = (1 << 31) - 1
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        while True:
            b = (ones ^ a) + 1
            #print('b =',b)
            if b <= a:
                break
            ones >>= 1
            if ones == 0:
                return ans
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())


### FIXED CODE ###

import sys
import collections

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = collections.Counter(A)

    ans = 0
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        b = (1 << a.bit_length()) - a
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

#  1  1  7   9
#     3  5   11
#        13
#     15
#  2  6  10
#     14
#  4  4  12
#
#  8
### BUGGY CODE ###

import os
import sys
from collections import defaultdict

from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = defaultdict(set)
for u, v in UV:
    graph[u].add(v)

vs = {S}
checked = set()
i = 0
prev = 0
while True:
    i += 1
    checked |= vs
    for _ in range(3):
        ss = set()
        for v in vs:
            ss |= graph[v]
        vs = ss
    if T in vs:
        print(i)
        break
    if len(checked) == prev:
        print(-1)
        break
    prev = len(checked)


### FIXED CODE ###

import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18

N, M = list(map(int, sys.stdin.readline().split()))
UV = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
S, T = list(map(int, sys.stdin.readline().split()))

graph = [[] for _ in range(N + 1)]
for u, v in UV:
    graph[u].append(v)

que = deque()
que.append((S, 0))
reached = np.zeros((N + 1, 3), dtype=bool)
reached[S, 0] = True

while que:
    u, step = que.popleft()
    for v in graph[u]:
        s = step + 1
        if not reached[v, s % 3]:
            reached[v, s % 3] = True
            que.append((v, s))
        if v == T and s % 3 == 0:
            print(s // 3)
            exit()
print(-1)
### BUGGY CODE ###

import math

ans = []
while True:
	try:
		n = int(raw_input())
		isPrime = [-1] * (n + 1)
		isPrime[0], isPrime[1] = False, False
		i = 2
		while i * i <= n:
			j = 2
			while j * i <= n:
			#for j in range(i, n+1 ,i):
				#print "%d,"%(j),
				isPrime[j * i] = False
				j += 1

			isPrime[i] = True
			i = isPrime.index(-1)
		ans.append(isPrime.count(True) + isPrime.count(-1))
	except EOFError:
		break
for num in ans:
	print num

### FIXED CODE ###

MAX = 1000000
prime = [1] * MAX
prime[0], prime[1] = 0, 0
i = 2
while i * i < MAX:
    j = 2
    while i * j < MAX:
        prime[i * j] = 0
        j += 1
    i += 1
for k in range(1, len(prime)):
    prime[k] += prime[k-1]

while True:
    try:
        n = int(raw_input())
        print prime[n]
    except EOFError:
        break
### BUGGY CODE ###

import math
from functools import reduce

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

K = int(input())
ans = 0
for a in range(1,K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      ans += gcd(a,b,c)

print(ans) 

### FIXED CODE ###

import math
from functools import reduce

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

K = int(input())
three = 0
six = 0
same = 0
for a in range(1,K+1):
  for b in range(a, K+1):
    for c in range(b, K+1):
      if(a != b and b != c and a != c):
        six += gcd(a,b,c)
      elif(a == b and b == c and c == a):
        same += a
      else:
        three += gcd(a,b,c)

print(six * 6 + three * 3 + same)
### BUGGY CODE ###

na,nb,nm = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
TA = []
for i in range(nm):
    m1, m2, m3 = map(int,input().split())
    T = a[m1-1]+b[m2-1]-m3
    TA.append(T)
for i in range(na):
    for j in range(nb):
        T = a[i] + b[j]
        TA.append(T)
TA = (sorted(TA))
print(TA[0])

### FIXED CODE ###

na,nb,nm = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
TA = []
for i in range(nm):
    m1, m2, m3 = map(int,input().split())
    T = a[m1-1]+b[m2-1]-m3
    TA.append(T)
T = min(a) + min(b)
TA.append(T)
print(min(TA))
### BUGGY CODE ###

from collections import Counter

class Levenshtein:

    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance

    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)

N = int(input())
S = input()

c = Counter(S)
S_target = 'R' * c['R'] + 'W' * c['W']

leven = Levenshtein(S, S_target)
print(leven.dist // 2)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()

c = Counter(S)
S_target = 'R' * c['R'] + 'W' * c['W']

ans = 0
for a, b in zip(S, S_target):
    if b == 'W':
        break
    if a != b:
        ans += 1
print(ans)
### BUGGY CODE ###

import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
csA = np.zeros((N+1), dtype=int)
for idx, i in enumerate(list(map(int, input().split()))):
    csA[idx+1] = csA[idx] + int(i)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)


### FIXED CODE ###

import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
# A = np.array(list(map(int, input().split())))
# csA = np.cumsum(A)

csA = [0] * (N+1)
for i, v in enumerate(input().split()):
    csA[i+1] = csA[i] + int(v)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)
### BUGGY CODE ###

from collections import defaultdict

n = int(input())
aaa = list(map(int, input().split()))
rd = defaultdict(set)
ma = 0
for i, a in enumerate(aaa):
    rd[a].add(i)
    ma = max(ma, a)

ma2 = 2
while ma2 <= ma:
    ma2 <<= 1

edges = [set() for _ in range(n)]
for i, a in enumerate(aaa):
    k = 2
    while k <= ma2:
        if k > a:
            b = k - a
            if b in rd:
                edges[i].update(j for j in rd[b] if i != j)
        k <<= 1


def dfs(v, visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


matched = [-1] * n

print(sum(dfs(s, set()) for s in range(n)) // 2)


### FIXED CODE ###

from collections import defaultdict

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


def solve(count):
    ans = 0
    for a in sorted(count, reverse=True):
        cnt = count[a]
        if cnt <= 0:
            continue
        ma = 1 << (a.bit_length())
        b = ma - a
        if b in count and count[b] > 0:
            if a == b:
                pair = cnt // 2
            else:
                pair = min(cnt, count[b])
                count[b] -= pair
            ans += pair
    return ans


count_e = defaultdict(lambda: 0)
count_o = defaultdict(lambda: 0)
for a in aaa:
    if a % 2 == 0:
        count_e[a] += 1
    else:
        count_o[a] += 1

print(solve(count_e) + solve(count_o))
### BUGGY CODE ###

N, K = map(int,input().split())
A = [0]+list(map(int,input().split()))

scores = []
for i in range(K,N+1):
    p = 1
    for k in range(K):
        p *= A[i-k]
    scores.append(p)

l = len(scores)-1
for i in range(l):
    print(["No","Yes"][scores[i+1]>scores[i]])

### FIXED CODE ###

N, K = map(int,input().split())
A = [0]+list(map(int,input().split()))

p = A[1]
for i in range(K+1,N+1):
    print(["No","Yes"][p < A[i]])
    p = A[i-K+1]
### BUGGY CODE ###

import math
import bisect

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

alist.sort()
#print(alist)

flist=[False]*N
answer=0
for i in reversed(range(N)):
  if flist[i]:
    continue
  
  p1=alist[i]
  p2=2**math.ceil(math.log(p1+1,2))-p1
  #print(p1,p2)
  
  index1 = bisect.bisect_left(alist,p2)  
  index2 = bisect.bisect_right(alist,p2)  
  #print(index1,index2)
  for j in range(index1,index2):
    if j != i and not flist[j]:
      flist[i]=True
      flist[j]=True
      answer+=1
      break
  
#print(flist)    
print(answer)


### FIXED CODE ###

import bisect
N=int(input())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

blist=[]
for a in alist:
  a2=a
  digit_a2=0
  while(a2>0):
    a2>>=1
    digit_a2+=1
  b=2**(digit_a2)-a
  blist.append(b)
#print(alist)
#print(blist)

dic_a={}
for a in alist:
  if a in dic_a:
    dic_a[a]+=1
  else:
    dic_a[a]=1

answer=0
for i in range(N):
  a=alist[i]
  b=blist[i]
  if a==b:
    if dic_a[a]>1:
      dic_a[a]-=2
      answer+=1
      #print(a,a)
  else:
    if dic_a[a]>0 and b in dic_a and dic_a[b]>0:
      dic_a[a]-=1
      dic_a[b]-=1
      answer+=1
      #print(a,b)
    
print(answer)
### BUGGY CODE ###

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

count = {}
for x in A:
    if count.get(x):
        count[x] += 1
    else:
        count[x] = 1

for i in range(N):
    count[A[i]] -= 1
    s = 0
    for x in count.values():
        s += x * (x - 1) // 2
    print(s)
    count[A[i]] += 1


### FIXED CODE ###

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

count = {}
for x in A:
    if count.get(x):
        count[x] += 1
    else:
        count[x] = 1

sub = {}
s = 0
for i, x in count.items():
    count[i] = x * (x - 1) // 2
    s += count[i]
    sub[i] = (x-1) * (x - 2) // 2

for i in range(N):
    print(s - count[A[i]] + sub[A[i]])
### BUGGY CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))


### FIXED CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))
### BUGGY CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X, Y, Z, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)

    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab + c)

    ABC.sort(reverse=True)

    print('\n'.join(map(str, ABC[:K])))

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    X, Y, Z, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    AB = []
    for a in A:
        for b in B:
            AB.append(a + b)

    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for ab in AB:
        for c in C:
            ABC.append(ab + c)

    ABC.sort(reverse=True)

    print('\n'.join(map(str, ABC[:K])))

    return


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

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

lr = [[0 for i in range(n)] for j in range(n)]

for i in range(m) :
    l,r = map(int,input().split())    
    lr[l-1][r-1] = lr[l-1][r-1] + 1

pq = []
for i in range(q) :
    pq.append(list(map(int,input().split())))

for i in range(q) :
    p = pq[i][0]
    q = pq[i][1]
    
    count = 0
    for j in range(p-1,q):
        for k in range(p-1,q):
            count += lr[j][k] 
    print(count)

### FIXED CODE ###

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

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

#for l in lr :        
#    print(l)
#print()

# 二次元累積和
for i in range(n) :
    for j in range(n) :
        left = 0
        btm  = 0
        mid  = 0

        if i > 0 :
            left = lr[j][i-1]
        if j > 0 :
            btm  = lr[j-1][i]
        if i > 0 and j > 0 :
            mid  = lr[j-1][i-1]
       
        lr[j][i] = lr[j][i] + left + btm - mid

#for l in lr :        
#    print(l)

ans=[] 
for i in range(q) :
    l,r = map(int,input().split())

    l = l - 1
    r = r - 1
    pre = 0
    if l > 0:    
        #print(lr[r][r],lr[l-1][r],lr[r][l-1],lr[l-1][l-1])
        pre = lr[l-1][r] + lr[r][l-1] - lr[l-1][l-1]     

    count = lr[r][r] - pre
    ans.append(count)

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

n,k = map(int,input().split())
mod = 10**9+7
v = [0]*(k+1)
ans = 0
for i in range(k,0,-1):
    if v[i] == 0:
        v[i] = ((k//i)**n-sum(v[i::i])) % mod
for i in range(k+1):
    ans += v[i]*i
    ans %= mod
print(ans)

### FIXED CODE ###

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

L,R=map(int,input().split())
l=L%2019
r=R%2019
l1=L//2019
r1=R//2019
if l1<r1:
  print(0)
elif l1==r1:
  res=[]
  for i in range(l,r):
    for j in range(i+1,r+1):
      if (i*j)%2019 not in res:
        res.append((i*j)%2019)
  print(min(res))

### FIXED CODE ###

l, r = map(int, input().split())

if l + 2019 <= r:
  print(0)
else:
  res = []
  for i in range(l, r+1):
     for j in range(i+1, r+1):
        res.append((i*j)%2019)
  print(min(res))
### BUGGY CODE ###

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

for i in range(m):
  b = max(a)
  a.remove(b)
  b = int(b/2)
  a.append(b)
  
print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))
### BUGGY CODE ###

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

As = sorted(list(map(int,input().split())))

Bs = []
Cs = []
for i in range(M):
	inputs = list(map(int,input().split()))
	Bs.append(inputs[0])
	Cs.append(inputs[1])

for j in range(1, M + 1):
	for n in range(Bs[j - 1]):
		if As[n] < Cs[j - 1]:
			As[n] = Cs[j - 1]
	As = sorted(As)

print(sum(As))

### FIXED CODE ###

import numpy as np

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

As = sorted(list(map(int,input().split())))
BCs = []

for i in range(M):
	inputs = list(map(int,input().split()))
	BCs.append(inputs)
BCs = sorted(BCs, reverse = True, key=lambda x: x[1])

index = 0
for bc in BCs:
	b = bc[0]
	c = bc[1]

	for n in range(b):
		try:
			if As[index] < c:
				As[index] = c
				index += 1
			else:
				break
		except:
			break
print(sum(As))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate
MOD = 10**9+7

def main():
  n, c = map(int, input().split())
  A = tuple(map(int, input().split()))
  B = tuple(map(int, input().split()))
  E = [[0]*(c+1) for _ in range(n)]
  for j in range(c+1):
    cumsum = tuple(pow(k, j, MOD) for k in range(401))
    cumsum = tuple(accumulate(cumsum))
    for i, (a, b) in enumerate(zip(A, B)):
      E[i][j] = cumsum[b] - cumsum[a-1]

  dp = [[0]*(c+1) for _ in range(n+1)]
  dp[0][0] = 1
  for i, e in enumerate(E):
    for j, f in enumerate(e):
      for k in range(c+1-j):
        dp[i+1][j+k] += dp[i][k]*f
  ans = dp[n][c]%MOD
  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate

MOD = 10**9+7

n, c = map(int, input().split())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
E = [[0]*(c+1) for _ in range(n)]
for j in range(c+1):
  cumsum = tuple(pow(k, j, MOD) for k in range(401))
  cumsum = tuple(i%MOD for i in accumulate(cumsum))
  for i, (a, b) in enumerate(zip(A, B)):
    E[i][j] = cumsum[b] - cumsum[a-1]

dp = [[0]*(c+1) for _ in range(n+1)]
dp[0][0] = 1
for i, e in enumerate(E):
  for j, f in enumerate(e):
    for k in range(c+1):
      if j+k <= c:
        dp[i+1][j+k] += dp[i][k]*f
        dp[i+1][j+k] %= MOD
ans = dp[n][c]
print(ans)
### BUGGY CODE ###

k=int(input())
f=0
import math
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            d=math.gcd(a,b)
            e=math.gcd(d,c)
            f+=e
print(f)


### FIXED CODE ###

import math
k=int(input())
ans=0
m_gcd=math.gcd
for h in range(1,k+1):
    for i in range(1,k+1):
        for j in range(1,k+1):
            ans+=m_gcd(m_gcd(h,i),j)
print(ans)
### BUGGY CODE ###

import numpy as np

k, q = map(int, input().split())
d = list(map(int, input().split()))
nxm = [map(int, input().split()) for _ in range(q)]

for n, x, m in nxm:
    dd = [e % m for e in d]
    dd = np.array(dd)

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

    print(ans)


### FIXED CODE ###

import numpy as np

k, q = map(int, input().split())
d = np.array(input().split(), np.int64)
nxm = [map(int, input().split()) for _ in range(q)]

for n, x, m in nxm:
    dd = d % m

    ans = n - 1
    divq, divr = divmod(n - 1, k)

    dd_r = dd[:divr]

    ans -= (k - np.count_nonzero(dd)) * divq
    ans -= divr - np.count_nonzero(dd_r)

    last = x + np.sum(dd) * divq + np.sum(dd_r)
    ans -= last // m - x // m

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

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
stop=set()
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
    elif e<0:
        stop.remove(x)
    elif len(stop)>0:
        ans[x]=min(stop)

print('\n'.join(map(str, ans)))

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

print('\n'.join(map(str, ans)))