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

import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7

edges = [[] for _ in range(N)]
chk = [[0]*N for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

res = K
def dfs(fr, to):
    global edges
    global chk
    global res
    chk[fr][to] += 1
    chk[to][fr] += 1
    addval = (K - sum(chk[fr]))
    res *= addval
    res %= mod
    for edge in edges[to]:
        if edge == fr:
            continue
        else:
            dfs(to, edge)
        
for p in edges[0]:
    dfs(0, p)

print(res)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import math
from itertools import permutations, combinations
from collections import defaultdict

sys.setrecursionlimit(10**7)
N, K = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7

edges = [[] for _ in range(N)]
for abi in ab:
    a, b = abi[0], abi[1]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

max_edges = max(list(map(len, edges)))
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


res = K
def dfs(last, cur):
    global res

    if last == -1:
        for i, np in enumerate(edges[0]):
            res *= (K-i-1)
            res %= mod
            dfs(0, np)

    else:
        num_edges_cur = len(edges[cur]) - 1
        if num_edges_cur == 0:
            return
        i = 0
        for i in range(K-2, K-num_edges_cur-2, -1):
            res *= i
            res %= mod
        for np in edges[cur]:
            if np == last:
                continue
            else:
                dfs(cur, np)
        
dfs(-1, 0)

print(res)
### BUGGY CODE ###

s = input()

count = 1

alphabets = {}

alphabets[s[0]] = 1

for i in range(1, len(s)):
    ss = s[0:i]
    for char, char_count in alphabets.items():
        if char != s[i]:
            count += char_count

    if s[i] in alphabets:
        alphabets[s[i]] += 1
    else:
        alphabets[s[i]] = 1

print(count)


### FIXED CODE ###

s = input()

count = 1

alphabets = {}

alphabets[s[0]] = 1

for i in range(1, len(s)):
    for char, char_count in alphabets.items():
        if char != s[i]:
            count += char_count

    if s[i] in alphabets:
        alphabets[s[i]] += 1
    else:
        alphabets[s[i]] = 1

print(count)
### BUGGY CODE ###

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

ans = 0
while True:
  for i in a_L:
    if i%2 != 0:
      print(ans)
      exit()
  ans += 1

    

### FIXED CODE ###

import sys

n = int(input())
a_L = list(map(int,input().split()))
counter = 0


while True:
    for val in a_L:
        if val % 2 != 0:
            print(counter)
            sys.exit(0)
    counter +=1
    a_L = [i/2 for i in a_L]
### BUGGY CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

from_cities = [[] for _ in range(N)]
for l, r in LR:
	l, r = l - 1, r - 1
	from_cities[l] += [r - l]

#print(from_cities)

for p, q in PQ:
	c, p, q = 0, p - 1, q - 1
	for i in range(p, q + 1):
		for line in from_cities[i]:
			if line <= q - i:
				c += 1
	print(c)



### FIXED CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

table = [[0 for _ in range(N + 2)] for _ in range(N + 2)]

for l, r in LR:
	table[l][r] += 1

#for line in table:
#	print(*line)
#print()

for i in range(1, N + 1):
	for j in range(1, N + 1):
		table[i][j] += table[i][j - 1]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		table[i][j] += table[i - 1][j]

#for line in table:
#	print(*line)
#print()

for p, q in PQ:
	#print(table[q][q], table[p - 1][q], table[q][p - 1], table[p - 1][p - 1])
	print(table[q][q] - table[p - 1][q] - table[q][p - 1] + table[p - 1][p - 1])
### BUGGY CODE ###

import numpy as np
N,M,K= map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

Asum=[0]*(N+1)
for i in range(N+1):
  Asum[i]=sum(A[0:i])
  if Asum[i]>K:
    Asum[i]=0
    Amax=i-1
    break
  Amax=i

Bsum=[0]*(M+1)
for i in range(M+1):
  Bsum[i]=sum(B[0:i])
  if Bsum[i]>K:
    Bsum[i]=0
    Bmax=i-1
    break
  Bmax=i
  
Csum=[0]*(Amax+1)*(Bmax+1)
for i in range(Amax+1):
  for j in range(Bmax+1):
    if Asum[i]+Bsum[j]>K:
      Csum[i*(Bmax+1)+j]=0
    else:Csum[i*(Bmax+1)+j]=Asum[i]+Bsum[j]

Cmax=max(Csum)
D=np.array([i for i, x in enumerate(Csum) if x == Cmax])
D=D//(Bmax+1)+D%(Bmax+1)
print(max(D))

### FIXED CODE ###

import numpy as np
import bisect
N,M,K= map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
if A[0]>K and B[0]>K:print(0);exit()

Asum=[0]
for i in range(N):
  if Asum[-1]+A[i]<=K:
    Asum.append(Asum[-1]+A[i])  
  else:break
    
Bsum=[0]
for j in range(M):
  if Bsum[-1]+B[j]<=K:
    Bsum.append(Bsum[-1]+B[j])
  else:break
    #AAsum=[]
#for i in range(len(Asum)):
#  AAsum.append(K-Asum[i])

#print(Asum)
#print(AAsum)
#print(Bsum)

C=[]
for i in range(len(Asum)):
  C.append(bisect.bisect(Bsum,K-Asum[i])+i-1)

#print(Asum)
#print(AAsum)
#print(Bsum)
#print(C)
print(max(C))
#176882
### BUGGY CODE ###

L, R = map(int, input().split())

min = (L*R)%2019

for i in range(L, R):
    for j in range(i+1, R+1):
        mod = (i*j)%2019
        if mod < min:
            min = mod

print(min)

### FIXED CODE ###

L, R = map(int, input().split())

if (R-L) >= 2018:
    print(0)
else:
    ans = 2019
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(ans, (i*j)%2019)
    print(ans)
### BUGGY CODE ###

N = int(input())
List =[]
for i in range(N):
    List.append(int(input()))

for i in range(N):
    temp = List[:]
    temp.pop(i)
    print(max(temp))



### FIXED CODE ###

N = int(input())
List =[]
for i in range(N):
    List.append(int(input()))

temp = sorted(List)

ma = temp[N-1]
se = temp[N-2]

for i in range(N):
    if (List[i] == ma):
        print(se)
    else:
        print(ma)
### BUGGY CODE ###

import math
import numpy as np
from functools import reduce

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

def gcd_list(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) :
           X = math.gcd(a, b)
           Y = math.gcd(X, c)
           ans += Y

print(ans)

### FIXED CODE ###

from math import gcd

K = int(input())

ans = 0

for a in range(1,K+1) :
    for b in range(1,K+1) :
        X = gcd(a, b)
        for c in range(1,K+1) :
           Y = gcd(X, c)
           ans += Y

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

import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n**(j-1) % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)


### FIXED CODE ###

import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)
### BUGGY CODE ###

#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, XOR, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, XOR, visit, i)
			XOR[node] ^= XOR[i] + 1

#処理内容
def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		x, y = getlist()
		x -= 1
		y -= 1
		G.add_edge(x, y)
		G.add_edge(y, x)

	#計算
	XOR = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, XOR, visit, 0)
	if XOR[0] == 0:
		print("Bob")
	else:
		print("Alice")
	

if __name__ == '__main__':
	main()

### FIXED CODE ###

#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def DFS(G, XOR, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, XOR, visit, i)
			XOR[node] ^= XOR[i] + 1

#処理内容
def main():
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		x, y = getlist()
		x -= 1
		y -= 1
		G.add_edge(x, y)
		G.add_edge(y, x)

	#計算
	XOR = [0] * N
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, XOR, visit, 0)
	if XOR[0] == 0:
		print("Bob")
	else:
		print("Alice")
	

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

C, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]

tmp = 1

for i in range(K):
  tmp = A[i] * tmp

for i in range(K,C):
  if tmp < (tmp / A[i-K]) * A[i]:
    print("Yes")
  else:
    print("No")
  tmp = (tmp / A[i-K]) * A[i]



### FIXED CODE ###

N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]

for i in range(N-K):
  if A[K+i] > A[i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

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

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 100
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -100
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)



### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
X=[]
n=0
for i in range(NM[0]):
  X.append(1)
  for j1 in AB:
    for j2 in j1:
      if j2==i+1:
        if j1.index(j2)==0:
          n=j1[1]
        else:
          n=j1[0]
        if H[i]<=H[n-1]:
          X[i]=0
x=0
for i in range(NM[0]):
  if X[i]==1:
    x+=1
print(x)

### FIXED CODE ###

import numpy as np
NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
X=np.ones(NM[0])
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
  if H[AB[i][0]-1]>H[AB[i][1]-1]:
    X[AB[i][1]-1]=0
  elif H[AB[i][0]-1]<H[AB[i][1]-1]:
    X[AB[i][0]-1]=0
  else:
    X[AB[i][1]-1]=0
    X[AB[i][0]-1]=0
x=0
for i in range(NM[0]):
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""
### BUGGY CODE ###

b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  t1,t2=0,0
  if i-b>0:
    t1=sum([cmb(i-1,x,mod) for x in range(b,i+1)])%mod
    t1*=pow(2,mod-1-i,mod)
    t1%=mod
    t-=t1
    t%=mod
  if i-w>0:
    t2=sum([cmb(i-1,x,mod) for x in range(w,i+1)])%mod
    t2*=pow(2,mod-1-i,mod)
    t2%=mod
    t+=t2
    t%=mod
  print(t)



### FIXED CODE ###

b,w=map(int,input().split())
dp=[0]*(b+w)
dp[0]=1/2
mod=pow(10,9)+7

def cmb(n,r,mod):
  if (r<0 or r>n):
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,b+w+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)
t1,t2=0,0
for i in range(1,1+b+w):
  t=pow(2,mod-2,mod)
  if i-b>0:
    t1*=2
    t1%=mod
    t1+=cmb(i-2,b-1,mod)
    t1%=mod
    tmp=t1*pow(2,mod-1-i,mod)
    tmp%=mod
    t-=tmp
    t%=mod
  if i-w>0:
    t2*=2
    t2%=mod
    t2+=cmb(i-2,w-1,mod)
    t2%=mod
    tmp=t2*pow(2,mod-1-i,mod)
    tmp%=mod
    t+=tmp
    t%=mod
  print(t)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = []
G = []
B = []

for i in range(N):
  if S[i] == 'R':
    R.append(i)
  elif S[i] == 'G':
    G.append(i)
  else:
    B.append(i)
    
count = 0

if len(R)>=max(len(G),len(B)):
  X = G
  Y = B
  Z = R
elif len(G)>=len(R):
  X = R
  Y = B
  Z = G
else:
  X = R
  Y = G
  Z = B

for r in X:
  for g in Y:
    len_B = len(Z)
    if (r+g)%2==0 and (r+g)//2 in Z:
      len_B -= 1
    if 2*r-g in Z:
      len_B -= 1
    if 2*g-r in Z:
      len_B -= 1
    count += len_B
      

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = 0
G = 0
B = 0

for i in range(N):
  if S[i] == 'R':
    R += 1
  elif S[i] == 'G':
    G += 1
  else:
    B += 1
    
count = 0
for i in range(N-1):
  for j in range(i+1,N):
    if 2*j-i>=N:
      break
    if S[i]!=S[j] and S[2*j-i]!=S[i] and S[2*j-i]!=S[j]:
      count += 1

print(R*G*B-count)
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=9**9]*h*w
d[~w+a*w+b]=1
q=[(a-1,b-1)]
for s,t in q:
 p=d[s*w+t]+1
 for y,x in(-1,0),(0,-1),(0,1),(1,0):
  for z in range(k):
   i,j=s+y*~z,t+x*~z
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[i*w+j]<p:break
   q+=(i,j),;d[i*w+j]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [0]*2019
for i in range(l):
    mod[int(s[i:])%2019] += 1

cnt += mod[0]

for i in range(1,2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))/2
print(int(cnt))


### FIXED CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [0]*2019
m = 0
for i in range(l):
    m = (int(s[l-1-i])*pow(10,i,2019) + m)%2019
    mod[m] += 1

cnt += mod[0]

for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))/2
        #print(i)
print(int(cnt))
### BUGGY CODE ###

N, K = map(int, input().split())
A_list = list(map(int, input().split()))
Score_list = [1 for i in range(N+1)]

for i in range(K, N+1):
    # print(sum(A_list[0:i]))
    #
    # Score_list[i] = sum(A_list[0:i])
    # Score_list[i] = 1
    if i == K:
        for j in range(i-K, i):
            Score_list[i] *= A_list[j]
    else:
        # print(i)
        # print(A_list[i])
        Score_list[i] = int(Score_list[i-1] * A_list[i-1] / A_list[i-1-K])
    if i > K:
        if Score_list[i] > Score_list[i-1]:
            print("Yes")
        else:
            print("No")
    # print(Score_list)

# print(Score_list)


### FIXED CODE ###

# import decimal
import time
time1 = time.time()

N, K = map(int, input().split())
# N = 200000
# K = 50000
A_list = list(map(int, input().split()))
# A_list = [2 for i in range(N)]
# Score_list = [1 for i in range(N+1)]

for i in range(K+1, N+1): #KからNの数字が入る
    # print(i-1)
    # print(i-2-K)
    if A_list[i-1] > A_list[i-1-K]:
        print("Yes")
    else:
        print("No")
    # if i == K:
    #     S = 1
    #     for j in range(i-K, i):
    #         S *= A_list[j]
    #     Score_list[i] = S
    # else:
    #     Score_list[i] = int(Score_list[i-1] / A_list[i-1-K])
    #     Score_list[i] *= A_list[i-1]
    # if i > K:
    #     if Score_list[i] > Score_list[i-1]:
    #         print("Yes")
    #     else:
    #         print("No")
    # # print(Score_list)

# print(Score_list)
time2 = time.time()
# print(time2-time1)
### BUGGY CODE ###

N = int(input())
#a,b = map(int,input().split())
A2 = list(map(int,input().split()))
A = list(set(A2))
#A = [int(input()) for i in range(N)]
#A = [list(map(int,input().split())) for i in range(N)]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    gcda = gcd(a,b)
    return a*b//gcda
def lcmlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        from functools import reduce
        return reduce(lcm,lista)
mod = 10**9 + 7
lcml = lcmlist(A)
ans = 0
for i in A2:
    ans = (ans + lcml//i)%mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
LCM = 1
for i in A:
    GCD = gcd(LCM,i)
    LCM = LCM*i//GCD
ans = 0
for i in A:
    ans += LCM//i
print(ans%mod)
### BUGGY CODE ###

N, A = map(int, input().split())
x = [int(i) for i in input().split()]

X = max(A, max(x))

dp = [[[0 for _ in range(N*X+1)] for _ in range(N+1)] for _ in range(N+1)]

for j in range(N+1):
    for k in range(N+1):
        for s in range(N*X+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s] = 0

ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]

print(ans)


### FIXED CODE ###

N, A = map(int, input().split())
x = [int(i) for i in input().split()]

X = max(A, max(x))

dp = [[[0 for _ in range(N*X+1)] for _ in range(N+1)] for _ in range(N+1)]

for j in range(N+1):
    for k in range(N+1):
        for s in range(N*X+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]+dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s] = 0

ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]

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

n,m=map(int,input().split())
cl=[list(map(int,input().split())) for i in range(m)]
pl=[[] for i in range(n)]
for p,y in cl:
    pl[p-1].append(y)
for i in range(n):
    pl[i].sort()
for p,y in cl:
    print('{0:06d}{1:06d}'.format(p,pl[p-1].index(y)+1))

### FIXED CODE ###

n,m=map(int,input().split())
py=[list(map(int,input().split()))+[i] for i in range(m)]
py.sort(key=lambda x:x[1])
ans=[]
cnt=[0]*n
for p,y,i in py:
    ans.append(['{0:06d}{1:06d}'.format(p,cnt[p-1]+1),i])
    cnt[p-1]+=1
ans.sort(key=lambda x:x[1])
for a,i in ans:
    print(a)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
p = 1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    p = p * a[i]
if p > 10**18:
    print(-1)
else:
    print(p)

### FIXED CODE ###

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

def ans(a):
    if 0 in a:
        return 0
    n = 1
    for i in a:
        n *= i
        if n > 10**18:
            return -1
    return n

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

N = int(input())
A = list(map(int, input().split()))
print(len([n for n in A if n == 1]))
for i, num in enumerate(A):
    ORG = A[:]
    ORG.pop(i)
    me = i + 2
    sub = len([n for n in ORG if n == me])
    print(sub)

### FIXED CODE ###

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

n,m=map(int,input().split())
*q, = map(int,input().split())
#print(q)
l = []
for _ in range(m):
  b,c = map(int,input().split())
  for i in range(b):
    l.append(c)
li = q+l
print(sum(sorted(li,reverse=True)[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
*q, = map(int,input().split())
#print(q)
l = [list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1], reverse=True)
#print(l)
for b,c in l:
  q.extend([c]*b)
  if len(q) > n*2:
    break

print(sum(sorted(q,reverse=True)[:n]))
### BUGGY CODE ###

import fractions
a, b = map(int, input().split())

def prime_factorize(n: int) -> list:
    ret = []
    for i in range(2, n*n+1):
        if n%i != 0: continue
        num = 0
        while n%i == 0:
            num += 1
            n /= i
        ret.append([i, num])

    if n != 1:
        ret.append([n, 1])

    return ret

g = fractions.gcd(b, a%b)
pf = prime_factorize(g)
print(len(pf)+1)


### FIXED CODE ###

import fractions
a, b = map(int, input().split())

def factorize(n: int) -> int:
    b = 2
    ret = []
    while b*b <= n:
        while n%b == 0:
            n //= b
            ret.append(b)
        b = b + 1

    if n > 1:
        ret.append(n)

    return list(set(ret))

g = fractions.gcd(a, b)
print(len(factorize(g))+1)
### BUGGY CODE ###

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

A.sort()
F.sort(reverse=True)

def target(x):
    train_count = 0
    for i in range(N):
        a = A[i]
        targ_a = x // F[i] 
        if targ_a < a:
            train_count += a - targ_a
    return train_count <= K

left = -1                            
right = A[-1] * F[0]                 
while right > left+1:                
    middle = (left + right) // 2     
    if target(middle):               
        right = middle               
    else:              
        left = middle 
print(right)


### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)