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

import sys
input = lambda: sys.stdin.readline().rstrip()

from heapq import heappop, heappush

X,Y,Z,K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

sum_list = []
seen_list = set()
ans = []

heappush(sum_list, (-(A[0]+B[0]+C[0]), 0, 0, 0))
seen_list.add((0, 0, 0))

while sum_list:
    s, i, j, k = heappop(sum_list)
    
    ans.append(str(-s))

    if i+1 < len(A) and (i+1, j, k) not in seen_list:
        heappush(sum_list, (-(A[i+1]+B[j]+C[k]), i+1, j, k))
        seen_list.add((i+1, j, k))

    if j+1 < len(B) and (i, j+1, k) not in seen_list:
        heappush(sum_list, (-(A[i]+B[j+1]+C[k]), i, j+1, k))
        seen_list.add((i, j+1, k))

    if k+1 < len(C) and (i, j, k+1) not in seen_list:
        heappush(sum_list, (-(A[i]+B[j]+C[k+1]), i, j, k+1))
        seen_list.add((i, j, k+1))

for i in range(0, K):
    print(ans[i])

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():

    from heapq import heappop, heappush, heapify
    X,Y,Z,K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    sum_list = []
    seen_list = set()
    ans = []

    heappush(sum_list, (-(A[0]+B[0]+C[0]), 0, 0, 0))
    seen_list.add((0, 0, 0))

    for _ in range(K):
        s, i, j, k = heappop(sum_list)
        
        ans.append(-s)

        if i+1 < len(A) and (i+1, j, k) not in seen_list:
            heappush(sum_list, (-(A[i+1]+B[j]+C[k]), i+1, j, k))
            seen_list.add((i+1, j, k))

        if j+1 < len(B) and (i, j+1, k) not in seen_list:
            heappush(sum_list, (-(A[i]+B[j+1]+C[k]), i, j+1, k))
            seen_list.add((i, j+1, k))

        if k+1 < len(C) and (i, j, k+1) not in seen_list:
            heappush(sum_list, (-(A[i]+B[j]+C[k+1]), i, j, k+1))
            seen_list.add((i, j, k+1))

    for i in range(0, K):
        print(ans[i])

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

from functools import cmp_to_key

n = int(input())
pref = []
suff = []

for i in range(n):
	s = input()
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])

# def comp1(x, y):
# 	return x[1] - y[1]
#
#
# def comp2(x, y):
# 	return -x[0] + y[0]


# pref.sort( key=cmp_to_key(comp1))
# suff.sort( key=cmp_to_key(comp2))

pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: -x[0])


pref = pref + suff

totPos = 0

for pos, neg in pref:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos

if totPos != 0:
	print("No")
else:
	print("Yes")


### FIXED CODE ###

n = int(input())
ara = [input() for _ in range(n)]
pref = []
suff = []

for s in ara:
	pos = neg = 0
	for ch in s:
		if ch == '(':
			pos += 1
		elif pos == 0:
			neg += 1
		else:
			pos -= 1
	if pos >= neg:
		pref.append([pos, neg])
	else:
		suff.append([pos, neg])


pref.sort(key=lambda x: x[1])
suff.sort(key=lambda x: x[0], reverse=True)

totPos = 0

ara = pref + suff

for pos, neg in ara:
	if neg > totPos:
		print("No")
		exit(0)
	totPos -= neg
	totPos += pos


if totPos != 0:
	print("No")
else:
	print("Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N,M,Q = map(int,input().split())
    acc = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l,r = map(int,input().split())
        acc[l][r] += 1
    pqs = [tuple(map(int,input().split())) for _ in range(Q)]
    for i in range(N):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for p,q in pqs:
        ans = 0
        for i in range(p,q+1):
            ans += acc[i][q]-acc[i][p-1]
        print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)
### BUGGY CODE ###

D=int(input())
c=input().split()
c=[int(a) for a in c]
S=[]
for _ in range(D):
    s=input().split()
    s=[int(a) for a in s]
    S.append(s)
T=[]
for _ in range(D):
    t=int(input())-1
    T.append(t)
M=int(input())
numbers=[]
for _ in range(M):
    d,q=map(int,input().split())
    numbers.append([d,q])
for m in range(M):
    ans = 0
    held = [0 for _ in range(26)]
    e=numbers[m][0]-1
    q=numbers[m][1]-1
    a=T[e]
    T[e]=q
    for d in range(D):
        s = S[d]
        place = T[d]
        held[place] = d + 1
        ans += s[place]
        for n in range(26):
            ans -= c[n] * (d + 1 - held[n])
    print(ans)


### FIXED CODE ###

D=int(input())
c=input().split()
c=[int(a) for a in c]
S=[]
for _ in range(D):
    s=input().split()
    s=[int(a) for a in s]
    S.append(s)
T=[]
for _ in range(D):
    t=int(input())-1
    T.append(t)
M=int(input())
numbers=[]
for _ in range(M):
    d,q=map(int,input().split())
    numbers.append([d,q])
whole=sum(c)
for m in range(M):
    ans = 0
    held = [0 for _ in range(26)]
    e=numbers[m][0]-1
    q=numbers[m][1]-1
    a=T[e]
    T[e]=q
    wholes=0
    for d in range(D):
        s = S[d]
        place = T[d]
        ans += s[place]
        wholes+=whole
        wholes-=c[place]*((d+1)-held[place])
        held[place] = d + 1
        ans-=wholes
    print(ans)
### BUGGY CODE ###

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

A = sorted(A)
B = sorted(B)
C = sorted(C)

# consider for each entry in B how many entries in C 
# exists which are larger than the entry...
BSC = [0]*N

# for this we will use binary search.
import bisect as bis

for i in range (0, N):
	BSC[i] = N-bis.bisect_right(C, B[i])

count = 0
# now we will loop over a...
for i in range (0, N):
	Upperpart = bis.bisect_right(B, A[i])
	count+=sum(BSC[Upperpart:])
    
print(count)

### FIXED CODE ###

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

A = sorted(A)
B = sorted(B)
C = sorted(C)

# for this we will use binary search.
import bisect as bis

BSC = [0]*N
ASB = [0]*N

for i in range (0, N):
	BSC[i] = N-bis.bisect_right(C, B[i])

for i in range (0, N):
	ASB[i] = bis.bisect_right(B, A[i])
    
for i in range (1, N):
	BSC[N-1-i] += BSC[N-i]

count = 0
for i in range (0, N):
	if ASB[i] ==N:
		continue
	else:
		count+=BSC[ASB[i]]

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

s = input()

c = ''
ans = 0
for i in range(len(s)):
    c = ''
    for j in range(i, len(s)):
        c += s[j]
        if int(c) % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()[::-1]

n = len(s)
cnt = [0] * 2019
cnt[0] = 1
total = 0
ans = 0
x = 1

for i in range(n):
    total += int(s[i]) * x
    total %= 2019
    x *= 10
    x %= 2019
    ans += cnt[total]
    cnt[total] += 1

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

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

def set2(nu):
    name = ''
    for i in range(30):
        m = nu%2
        if(m == 0):
            name = '0' + name
        else:
            name = '1' + name
        nu  = nu // 2
    return name

b = []
for i in range(n):
    b.append(set2(a[i]))

def xor(a,b):
    if(a == '0' and b == '0'):
        return '0'
    elif(a == '1' and b == '1'):
        return '0'
    else:
        return '1'

def xor2(A,B):
    C = ''
    for i in range(30):
        C = C + xor(A[i],B[i])
    return C

samu = '0'*30
for i in range(n):
    samu = xor2(samu,b[i])

c = []
for i in range(n):
    X = xor2(samu,b[i])
    num = 0
    d = 1
    for j in range(30):
        if(X[30-j-1]=='1'):
            num += d
        d *= 2
    c.append(num)

print(*c)


### FIXED CODE ###

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

samu = 0
for i in range(n):
    samu = samu^a[i]

c = []
for i in range(n):
    num = samu^a[i]
    c.append(num)

print(*c)
### BUGGY CODE ###

n, m = map(int, input().split())
ac = []
for _ in range(m):
    a,_ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    ac.append([a, c])
dp = [float('inf')] * 2**n
dp[0] = 0
for s in range(2**n):
    for a, c in ac:
        t = s|c
        cost = dp[s] + a
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
ac = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    ac.append([a, c])
dp = [float('inf')] * 2**n
dp[0] = 0
for s in range(2**n):
    for a, c in ac:
        t = s|c
        if dp[t] > dp[s] + a:
            dp[t] = dp[s] + a
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)
### BUGGY CODE ###

import numpy as np

def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = 1
        pre = s[i]
    t = np.array(t)
    for _ in range(q):
        l, r = map(int, input().split())
        print(sum(t[l:r]))
        
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    t_sum = 0
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = t_sum + 1
            t_sum +=  1
        else: 
            t[i] = t_sum
        pre = s[i]
    for _ in range(q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])
        
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math

n, q = map(int, input().split(" "))
s = input()

lrL = [list(map(int, input().split(" "))) for _ in range(q)]

idx = []
# n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        idx.append(i)

for l, r in lrL:
    cnt = 0
    for x in idx:
        if x > r - 2:
            break
        if l - 1 <= x <= r - 2:
            cnt += 1
    print(cnt)


### FIXED CODE ###

import math

n, q = map(int, input().split(" "))
s = input()

lrL = [list(map(int, input().split(" "))) for _ in range(q)]

li = [0] * n
mx = 0
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        mx += 1
    li[i + 1] = mx

for l, r in lrL:
    print(li[r - 1] - li[l - 1])
### BUGGY CODE ###

MOD = 10 ** 9 + 7

lcm = dict()

def prime_factorize(n):
    a = dict()
    while not n & 1:
        a[2] = a.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            a[f] = a.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] = a.get(n, 0) + 1
    global lcm
    for key, value in a.items():
        lcm[key] = max(lcm.get(key, 0), value)
    return a

N = int(input())
A = map(int, input().split())
A_factored = [prime_factorize(a) for a in A]

total = 0
for a in A_factored:
    d = lcm.copy()
    for key, value in a.items():
        d[key] -= value
    n = 1
    for key, value in d.items():
        n *= key ** value
    total += n % MOD
    total %= MOD

print(total)


### FIXED CODE ###

import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

l = 1
for a in A:
    l = lcm(l, a)

total = 0
for a in A:
    total += l // a

print(total % LARGE)
### BUGGY CODE ###

import numpy as np
from numba import jit
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())))

def loop(a,k):
  if k>41:
    ans=np.ones(N)*N
  else:
    ans=a
    for j in range(k):
      B=np.zeros(N+1)
      for i in range(N):
        B[max(0,i-int(ans[i]))] +=1
        B[min(N,i+int(ans[i])+1)] -=1
      ans=np.cumsum(B)[:N]
  return ans

for i in loop(A,K):
  print(int(i))

### FIXED CODE ###

import numpy as np
from numba import jit
N,K=map(int,input().split())
A=np.array(list(map(int,input().split())),dtype=np.int64)
@jit
def loop(a,k):
  if k>41:
    ans=np.ones(N,dtype=np.int64)*N
  else:
    ans=a
    for j in range(k):
      B=np.zeros(N+1,dtype=np.int64)
      for i in range(N):
        B[max(0,i-int(ans[i]))] +=1
        B[min(N,i+int(ans[i])+1)] -=1
      ans=np.cumsum(B)[:N]
  return ans

for i in loop(A,K):
  print(i)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n = int(input())
    s = input()
    x = 1

    sn = [ord(c) - 96 + x for c in s]

    lmax = n // 2
    m1 = 10 ** 9 + 7
    m2 = 2 ** 61 - 1

    ans = 0

    for l in range(1, lmax + 1):
        appeared = set()
        diff = pow(m1, l - 1, m2)

        h_init = 0
        for i in range(l):
            h_init += sn[i] * pow(m1, l - 1 - i, m2)

        hashlist = [0] * n
        hashlist[0] = h_init
        h = h_init

        for i in range(l, n):
            h -= sn[i-l] * diff
            h *= m1
            h += sn[i]
            h %= m2
            hashlist[i] = h
            if i - l >= 0:
                appeared.add(hashlist[i-l])
            if h in appeared:
                ans = l
                break

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    s = input()
    x = 1

    sn = [ord(c) - 96 + x for c in s]

    lmax = n // 2
    m1 = 10 ** 9 + 7
    m2 = 2 ** 61 - 1

    ans = 0

    ng = n + 1
    ok = 0

    while abs(ng - ok) > 1:
        l = (ng + ok) // 2
        found = False

        appeared = set()
        diff = pow(m1, l - 1, m2)

        h_init = 0

        for i in range(l):
            h_init += sn[i] * pow(m1, l - 1 - i, m2)
            h_init %= m2

        hashlist = [0] * n
        hashlist[l - 1] = h_init
        h = h_init

        for i in range(l, n):
            h -= sn[i - l] * diff
            h *= m1
            h += sn[i]
            h %= m2
            hashlist[i] = h
            if i - l >= 0:
                appeared.add(hashlist[i - l])
            if h in appeared:
                found = True
                break

        if found:
            ok = l
        else:
            ng = l

    print(ok)


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

h, n = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]

max_a = max(a)[0]

dp = [float('inf') for i in range(h + max_a + 1)]
dp[0] = 0
for i in range(1, h+max_a + 1):
    dp_ = dp[i]
    for damage in a:
        if i < damage[0]:
            dp_ = min(dp_, damage[1])
        else:
            dp_ = min(dp_, dp[i-damage[0]] + damage[1])
    dp[i] = dp_

print(dp[h])

### FIXED CODE ###

h, n  = map(int,input().split())
am = [list(map(int, input().split())) for i in range(n)] 

dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp_val = dp[i]
    for a, m in am:
        if a >= i:#overkill
            dp_val = min(dp_val, m)
        else:
            dp_val = min(dp_val, dp[i-a]+m)
    dp[i] = dp_val
print(dp[h])
### BUGGY CODE ###

import bisect


N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = sorted([int(input()) for i in range(Q)])
time = {}
for q in querys:
    time[q] = -1

check_parsed = []
for s, f, x in check_points:
    start, end = [s-x, f-x]
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_left(querys, end)
    for q in querys[left:right]:
        if time[q] == -1 or time[q] >= x:
            time[q] = x


for q in querys:
    print(time[q])


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

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

dp = [0 for _ in range(W + 1)]
for w, v in WV:
	for tw in range(W, w - 1, -1):
		dp[tw] = max(dp[tw], dp[tw - w] + v)
	#print(dp)
print(max(dp))


### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))

def sieve_Eratosthenes(n):
    f = [True]*(n+1)
    f[0] = False
    f[1] = False
    m = int(n**0.5+1)
    for i in range(2,m):
        if f[i]:
            for j in range(i*i,n+1, i):
                f[j] = False
    return f

def getPrimeLists(n):
    table = sieve_Eratosthenes(n)
    return [x for x in range(2,n+1) if table[x]]

primes = getPrimeLists(10**6+10)
for p in primes:
    if N - np.count_nonzero(A % p) > 1:
        break
else:
    print('pairwise coprime')
    exit()

allgcd = np.gcd.reduce(A)
if allgcd == 1:
    print('setwise coprime')
    exit()

print('not coprime')


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

def gcd(a,b):
    while b:
        a,b = b, a%b
    return a

def sieve_Eratosthenes(n):
    f = [True]*(n+1)
    f[0] = False
    f[1] = False
    m = int(n**0.5+1)
    for i in range(2,m):
        if f[i]:
            for j in range(i*i,n+1, i):
                f[j] = False
    return f

def getPrimeLists(n):
    table = sieve_Eratosthenes(n)
    return [x for x in range(2,n+1) if table[x]]

def primeFactorization(n):
    res = defaultdict(int)
    m = int(n**0.5)
    for i in range(2,m+1):
        while n % i == 0:
            n = n//i
            res[i] += 1
    if n > 1:
        res[n] = 1
    return res

table = [0] * (10**6+10)
f = False
for a in A:
    pf = primeFactorization(a).keys()
    for p in pf:
        if table[p] > 0:
            f = True
        table[p] += 1
    if f:
        break
else:
    print('pairwise coprime')
    exit()

allgcd = reduce(gcd, A)
if allgcd == 1:
    print('setwise coprime')
    exit()

print('not coprime')
### BUGGY CODE ###

N = int(input())
p = list(map(float,input().split()))
# dp[i][j] コインiまで投げて表の個数がjとなる確率
dp = [[0] * (N+1) for i in range(N+1)]
dp[1][1] = p[0]
dp[1][0] = 1 - p[0]
for i in range(2,N+1):
    dp[i][0] = dp[i-1][0] * (1 - p[i-1])
    for j in range(1,N+1):
        dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1 - p[i-1])
ans = sum(dp[N][(N+1)//2:])
print(ans)

### FIXED CODE ###

N = int(input())
p = list(map(float,input().split()))
# dp[i][j] コインiまで投げて表の個数がjとなる確率
dp = [[0] * (N+1) for i in range(N+1)]
dp[1][1] = p[0]
dp[1][0] = 1 - p[0]
for i in range(2,N+1):
    dp[i][0] = dp[i-1][0] * (1 - p[i-1])
    for j in range(1,N+1):
        dp[i][j] = dp[i-1][j-1] * p[i-1] + dp[i-1][j] * (1 - p[i-1])
ans = sum(dp[N][(N+1)//2:])
print(ans)
### BUGGY CODE ###

from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 998244353)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
mem = []
mappend = mem.append
for x in mempow(M-1,N-1):
    mappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    for i in range(K+1):
        ans = (ans + (comb(N-1,i)*M*mem[N-i-1])) % 998244353
    print(ans)

### FIXED CODE ###

from functools import reduce
import math
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 998244353
def comb(n,r,m):
    if r == 0: return 1
    return memf[n]*pow(memf[r],m-2,m)*pow(memf[n-r],m-2,m)
def mempow(a,b):
    temp = 1
    yield temp
    for i in range(b):
        temp = temp * a % 998244353
        yield temp
def memfact(a):
    temp = 1
    yield temp
    for i in range(1,a+1):
        temp = temp * i % 998244353
        yield temp

N,M,K = (int(x) for x in input().split())
memp = []
memf = []
mpappend = memp.append
mfappend = memf.append
for x in mempow(M-1,N-1):
    mpappend(x)
for x in memfact(N-1):
    mfappend(x)
ans = 0
if M == 1:
    if K + 1 < N:
        print('0')
    else:
        print('1')
else:
    i = 0
    for i in range(K+1):
        ans = (ans + (comb(N-1,i,998244353)*M*memp[N-i-1])) % 998244353
    print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

d = {}
for i in s:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1

l = []
for k in d.keys():
    if d[k] == max(d.values()):
        l.append(k)

l_s = sorted(l)
                
for ans in l_s:
    print(ans)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]

d = {}
for i in s:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1
        
m = max(d.values())

l = []
for k in d.keys():
    if d[k] == m:
        l.append(k)

l_s = sorted(l)
                
for ans in l_s:
    print(ans)
### BUGGY CODE ###

n, a, b, c, d = map(int, raw_input().split())
MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)
rcd = range(c, d+1)

dp = [0]*(n+1)
dp[0] = 1

for i in xrange(1, n+1):
    v = fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(v, MOD-2, MOD)
Y = [None]*(d+1-c)
for g in xrange(a, b+1):
    y = frev[g]
    Y[:min(d,n/g)+1-c] = (pow(y, j, MOD)*frev[j] for j in xrange(c, min(d, n/g)+1))
    dp[::-1] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] for j in xrange(c, min(d, i/g)+1)) % MOD for i in rn)
print dp[n]%MOD

### FIXED CODE ###

n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    for i in rn:
        x = frev[n-i]
        dp[i] = (dp[i] + sum(dp[i-g*j] * fact[n-i+g*j] * x * pow(y, j, MOD) * frev[j] for j in xrange(c, min(d, i/g)+1))) % MOD
print dp[n]