Read problems statements in Mandarin Chinese  and Russian  

Eugene has a sequence of upper hemispheres and another of lower hemispheres. The first set consists of N upper hemispheres indexed 1 to N and the second has M lower hemispheres indexed 1 to M. The hemispheres in any sequence can have different radii.
He is now set out on building spheres using them. To build a sphere of radius R, he must take one upper half of the radius R and one lower half of the radius R. Also, he can put a sphere into a bigger one and create a sequence of nested concentric spheres. But he can't put two or more spheres directly into another one.
Examples: 

If there is a sequence of (D+1) nested spheres, we can call this sequence as a D-sequence.

Eugene has to find out how many different X-sequence are possible (1 ≤ X ≤ C). An X sequence is different from another if the index of any of the hemisphere used in one X-sequence is different from the other. Eugene doesn't know how to do it, so Chef agreed to help him. Of course, Chef is too busy now and he asks you to help him.

------ Input ------ 

The first line contains a three integers: N denoting the number of upper sphere halves, M denoting the number of lower sphere halves and C.
The second line contains N space-separated integers U_{1}, U_{2}, ..., U_{N} denoting the radii of upper hemispheres.
The third line contains M space-separated integers L_{1}, L_{2}, ..., L_{M} denoting the radii of lower hemispheres.

------ Output ------ 

Output a single line containing C space-separated integers D_{1}, D_{2}, ..., D_{C}, where D_{i} is the number of ways there are to build i-sequence in modulo 10^{9}+7.

------ Constraints ------ 

$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ C ≤ 10^{3}$
$1 ≤ U_{i} ≤ C$
$1 ≤ L_{i} ≤ C$

------ Subtasks ------ 

$Subtask 1:  1 ≤ N, M, C ≤ 10 - 15 points$
$Subtask 2: 1 ≤ N, M, C ≤ 100 - 25 points$
$Subtask 3: Original constraints - 60 points$

----- Sample Input 1 ------ 
3 4 3
1 2 3
1 1 3 2
----- Sample Output 1 ------ 
5 2 0
----- explanation 1 ------ 

We can build spheres with such radii:
R=1 and there are 2 ways to do it. (We can choose any of 2 lower hemispheres with R=1)
R=2 and there is 1 way to do it.
R=3 and there is 1 way to do it.

We can build these 1-sequences:
1->2 and there are 2 ways to do it. ( sphere with radius 1 is inside sphere with radius 2, we can choose any of 2 ways of building sphere with radius 1)
1->3 and there are 2 ways to do it.
2->3 and there is 1 way to do it.

2 + 2 + 1 = 5

We can build these 2-sequences:
1->2->3 and there are 2 ways to do it.

We can't build 3-sequences, because we don't have 4 spheres of different radii.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import collections
import sys
import copy
mod = 10 ** 9 + 7

def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree
[n, m, c] = [int(i) for i in input().split()]
uh = collections.Counter([int(i) for i in input().split()])
lh = collections.Counter([int(i) for i in input().split()])
l = []
for i in uh:
	if i in lh:
		l.append([i, uh[i] * lh[i]])
l.sort()
freq = [i[1] for i in l]
n = len(freq)
arr = [0] * n
BITTree = construct(freq, n)
for i in range(1, c + 1):
	if i + 1 <= n:
		BITTreePresent = construct(arr, n)
		for j in range(i, n):
			updatebit(BITTreePresent, n, j, getsum(BITTree, j - 1) * freq[j] % mod)
		print(getsum(BITTreePresent, n - 1) % mod, end=' ')
		BITTree = BITTreePresent
	else:
		print(0, end=' ')


from collections import Counter
(n, m, c) = map(int, input().split())
up = Counter(list(map(int, input().split())))
down = Counter(list(map(int, input().split())))
dp = [[0 for _ in range(c + 1)] for _ in range(c + 1)]
for i in range(1, c + 1):
	dp[0][i] = (dp[0][i - 1] + up.get(i, 0) * down.get(i, 0)) % (10 ** 9 + 7)
for i in range(1, c + 1):
	for j in range(1, c + 1):
		dp[i][j] = (dp[i][j - 1] + up.get(j, 0) * down.get(j, 0) * dp[i - 1][j - 1]) % (10 ** 9 + 7)
for i in range(1, c + 1):
	print(dp[i][c], end=' ', sep='')
print()


(n, m, c) = map(int, input().split())
lst1 = list(map(int, input().split()))
lst2 = list(map(int, input().split()))
mod = 10 ** 9 + 7
up = [0 for _ in range(c + 2)]
lo = [0 for _ in range(c + 2)]
for i in range(n):
	up[lst1[i]] += 1
for i in range(m):
	lo[lst2[i]] += 1
dp = [[0 for _ in range(1005)] for _ in range(1005)]
for i in range(1, c + 2):
	dp[0][i] = (dp[0][i - 1] % mod + up[i] % mod * (lo[i] % mod) % mod) % mod
for i in range(1, c + 1):
	for j in range(1, c + 1):
		dp[i][j] = (dp[i - 1][j - 1] % mod * up[j] % mod * lo[j] % mod % mod + dp[i][j - 1] % mod) % mod
	print(dp[i][c], end=' ')


import sys
info = list(map(int, sys.stdin.readline().split(' ')))
list1 = list(map(int, sys.stdin.readline().split(' ')))
list2 = list(map(int, sys.stdin.readline().split(' ')))
numbers1 = [0] * (1 + max(list1))
numbers2 = [0] * (1 + max(list2))
for i in range(len(list1)):
	numbers1[list1[i]] = numbers1[list1[i]] + 1
for i in range(len(list2)):
	numbers2[list2[i]] = numbers2[list2[i]] + 1
if max(list1) <= max(list2):
	a = max(list1)
	b = max(list2)
else:
	a = max(list2)
	b = max(list1)
if b <= info[0]:
	b = info[0]
numbers3 = [0] * (b + 1)
for i in range(a + 1):
	numbers3[i] = numbers1[i] * numbers2[i]
result = [0] * (1 + b)
result[0] = result[0] + numbers3[1]
for i in range(2, b + 1):
	if numbers3[i] != 0:
		old = list(result)
		result[0] = result[0] + numbers3[i]
		for j in range(1, i):
			result[j] = numbers3[i] * old[j - 1] + old[j]
for i in range(1, info[2] + 1):
	result[i] = result[i] % 1000000007
	print(str(result[i]), end=' ')


inp = list(map(int, input().split()))
U = list(map(int, input().split()))
max1 = max(U)
sum2 = 0
sum3 = 0
z = 1
L = list(map(int, input().split()))
f = list((0 for i in range(1, 100001)))
f1 = list((0 for i in range(1, 100001)))
fa = list((0 for i in range(1, inp[2] + 2)))
l1 = list((0 for i in range(1, 100001)))
u1 = list((0 for i in range(1, 100001)))
for i in L:
	l1[i] += 1
for i in U:
	u1[i] += 1
for j in range(max1, 0, -1):
	f[j] = l1[j] * u1[j]
	f1[j] = f[j]
	sum2 += f[j]
for j in range(1, max1 + 1):
	for i in range(1, max1 - j + 1):
		sum2 -= f1[i]
		f1[i] = f[i] * sum2
		sum3 += f1[i]
	sum2 = sum3
	fa[z] = sum3
	sum3 = 0
	z += 1
for i in range(1, inp[2] + 1):
	print(fa[i] % 1000000007, end=' ')


import time
l = [0] * 1002
u = [0] * 1002
r = []
(n, m, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
for i in range(n):
	u[a[i]] += 1
a = [int(x) for x in input().split()]
for i in range(m):
	l[a[i]] += 1
j = 0
for i in range(1001):
	if l[i] * u[i] != 0:
		r.append(l[i] * u[i])
		j += 1
r.append(0)
x = []
for i in range(k + 1):
	sum = r[0]
	x.append([0] * j)
	for ii in range(j):
		if i == 0 or ii == 0:
			x[i][ii] = 0
		elif i > ii:
			x[i][ii] = 0
		elif i == 1:
			x[i][ii] = (x[i][ii - 1] + r[ii] * sum) % 1000000007
			sum = (sum + r[ii]) % 1000000007
		else:
			x[i][ii] = (x[i - 1][ii - 1] * r[ii] + x[i][ii - 1]) % 1000000007
for i in range(1, k + 1):
	print(x[i][j - 1] % 1000000007, end=' ')


mod = 10 ** 9 + 7
MAX = 10 ** 3 + 5
(n, m, c) = map(int, input().split())
(h1, h2, v1, ans) = ([0] * MAX, [0] * MAX, [], [])
(l1, l2) = ([int(i) for i in input().split()], [int(i) for i in input().split()])
for i in range(len(l1)):
	h1[l1[i]] += 1
for i in range(len(l2)):
	h2[l2[i]] += 1
for i in range(MAX):
	if h1[i] > 0 or h2[i] > 0:
		v1.append(h1[i] * h2[i])
l = len(v1)
dp = [[0 for x in range(l)] for x in range(l)]
for i in range(l):
	if i == 0:
		for j in range(i + 1, l):
			dp[i][j] += dp[i][j - 1]
			x = i
			for k in range(x, j):
				dp[i][j] += v1[k] * v1[j]
	else:
		for j in range(i + 1, l):
			dp[i][j] += dp[i - 1][j - 1] * v1[j] + dp[i][j - 1]
	ans.append(dp[i][l - 1])
if l < c:
	for i in range(l):
		print(ans[i] % mod, end=' ')
	for i in range(l, c):
		print('0', end=' ')
else:
	for i in range(c):
		print(ans[i] % mod, end=' ')


import math
A = [int(x) for x in input().split()]
(n, m, c, maxx) = (A[0], A[1], A[2], 0)
u = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
U = [int(0) for x in range(1002)]
L = [int(0) for x in range(1002)]
for i in range(n):
	U[u[i]] += 1
	if u[i] > maxx:
		maxx = u[i]
for i in range(m):
	L[l[i]] += 1
	if l[i] > maxx:
		maxx = l[i]
a = [int(0) for x in range(maxx + 1)]
(a[0], k) = (0, 1)
for i in range(maxx + 1):
	if U[i] * L[i] != 0:
		a[k] = U[i] * L[i] % 1000000007
		k += 1
k -= 1
b = [[int(0) for x in range(1005)] for y in range(1005)]
for j in range(1, k + 1):
	b[0][j] = (b[0][j - 1] + a[j]) % 1000000007
for i in range(1, k):
	for j in range(i + 1, k):
		b[i][j] = (b[i][j - 1] + b[i - 1][j - 1] * a[j]) % 1000000007
sum = 0
for i in range(k):
	sum = 0
	for j in range(i + 1, k):
		sum = (sum + b[i][j] * a[j + 1]) % 1000000007
	print(sum, end=' ')
for i in range(k, c):
	print('0', end=' ')


from itertools import chain
(n, m, c) = map(int, input().split())
u = list(map(int, input().split()))
l = list(map(int, input().split()))
upper = [0] * 1001
lower = [0] * 1001
rcount = []
for i in range(m):
	lower[l[i]] += 1
for i in range(n):
	upper[u[i]] += 1
for i in range(1001):
	if upper[i] * lower[i] != 0:
		rcount.append(upper[i] * lower[i])
ans = [1]
for i in rcount:
	ans = [(p + q * i % 1000000007) % 1000000007 for (p, q) in zip(chain([0], ans), chain(ans, [0]))]
length = len(rcount)
a = []
for i in range(length - 2, -1, -1):
	a.append(ans[i])
length = len(a)
for i in range(0, c):
	if i > length - 1:
		print(0, end=' ')
	else:
		print(a[i], end=' ')


import sys
(n, m, c) = map(int, input().split())
u = []
l = []
uln = []
u = map(int, sys.stdin.readline().split())
l = map(int, sys.stdin.readline().split())
un = [0] * c
ln = [0] * c
uln = [0] * c
for i in u:
	un[i - 1] += 1
for i in l:
	ln[i - 1] += 1
for i in range(c):
	uln[i] = un[i] * ln[i]
f = {}
f[1, 1] = uln[0]
for i in range(2, len(uln) + 1):
	f[1, i] = f[1, i - 1] + uln[i - 1]
for j in range(2, len(uln) + 1):
	for i in range(2, len(uln) + 1):
		if i < j:
			f[i, j] = f[i, j - 1] + f[i - 1, j - 1] * uln[j - 1]
		elif i == j:
			f[i, j] = f[i - 1, j - 1] * uln[j - 1]
		else:
			pass
for i in range(2, c + 1):
	sys.stdout.write(str(f[i, c] % (10 ** 9 + 7)) + ' ')
print(0)


import sys
input = sys.stdin.readline
modulus = 10 ** 9 + 7
(n, m, cs) = [int(i) for i in input().split()]
ns = [int(i) for i in input().split()]
ms = [int(i) for i in input().split()]
ncs = [0] * (cs + 1)
mcs = [0] * (cs + 1)
for ni in ns:
	ncs[ni] += 1
for mi in ms:
	mcs[mi] += 1
scs = [ncs[i] * mcs[i] for i in range(cs + 1)]
while 0 in scs:
	scs.remove(0)
output = ''
psums = scs.copy()
for c in range(1, cs + 1):
	nsums = []
	runningsum = 0
	for (r, s) in zip(scs[c:], psums):
		runningsum += s
		runningsum %= modulus
		nsums.append(r * runningsum % modulus)
	output += str(sum(nsums) % modulus) + ' '
	psums = nsums
output.rstrip()
print(output)


s = input()
x = s.split(' ')
n = int(x[0])
m = int(x[1])
c = int(x[2])
s = input()
upper = s.split(' ')
s = input()
lower = s.split(' ')
upper = list(map(int, upper))
lower = list(map(int, lower))
upper.sort()
lower.sort()
if lower[m - 1] > upper[n - 1]:
	max = lower[m - 1]
else:
	max = upper[n - 1]
combinations = [0] * max
cumulative = [0] * max
indexU = 0
indexL = 0
cU = 0
cL = 0
total = 0
for i in range(0, max):
	while indexU < n and upper[indexU] == i + 1:
		cU += 1
		indexU += 1
	while indexL < m and lower[indexL] == i + 1:
		cL += 1
		indexL += 1
	combinations[i] = cU * cL
	cU = 0
	cL = 0
cumulative[0] = combinations[0]
for i in range(1, max):
	cumulative[i] = cumulative[i - 1] + combinations[i]
mod = 1000000007
for i in range(1, c + 1):
	newArray = [0] * max
	for j in range(i, max):
		total += cumulative[j - 1] % mod * (combinations[j] % mod) % mod
		total = total % mod
		newArray[j] = newArray[j - 1] % mod + cumulative[j - 1] % mod * (combinations[j] % mod) % mod
	print(total, end=' ')
	cumulative = newArray
	total = 0


def solve(N, M, C, U, L):
	u = {}
	l = {}
	for i in U:
		if i in u:
			u[i] += 1
		else:
			u[i] = 1
	for i in L:
		if i in l:
			l[i] += 1
		else:
			l[i] = 1
	c = {}
	for i in u:
		if i in l:
			c[i] = u[i] * l[i]
	c = list(c.items())
	c.sort()
	c.reverse()
	res = [[0] * len(c)]
	for col in range(len(c) - 1, -1, -1):
		if col == len(c) - 1:
			res[0][col] = c[col][1]
		else:
			res[0][col] = res[0][col + 1] + c[col][1]
	for row in range(1, C):
		res.append([0] * len(c))
		for col in range(len(c) - row - 1, -1, -1):
			res[row][col] = c[col][1] * res[row - 1][col + 1] + res[row][col + 1]
	res.append([0] * len(c))
	q = []
	for i in res[1:]:
		q.append(str(i[0] % 1000000007))
	return ' '.join(q)

def main(infile, outfile):
	(N, M, C) = [int(x) for x in infile.readline().split()]
	U = [int(x) for x in infile.readline().split()]
	L = [int(x) for x in infile.readline().split()]
	outfile.write(str(solve(N, M, C, U, L)) + '\n')
from sys import stdin, stdout
main(stdin, stdout)


(n, m, c) = map(int, input().split())
l = list(map(int, input().split()))
upper = [0] * 1001
for i in l:
	upper[i] += 1
l = list(map(int, input().split()))
lower = [0] * 1001
for i in l:
	lower[i] += 1
mod = 10 ** 9 + 7
spheres = []
for i in range(1001):
	if upper[i] != 0 and lower[i] != 0:
		spheres.append(upper[i] * lower[i] % mod)
total = len(spheres)
sph = spheres[:]
cumu = [0] * len(sph)
for k in range(1, c + 1):
	if k >= total:
		print(0, end=' ')
		continue
	cumu[k - 1] = sph[k - 1]
	ans = 0
	for i in range(k, total):
		cumu[i] = (cumu[i - 1] + sph[i]) % mod
		sph[i] = spheres[i] * cumu[i - 1] % mod
		ans = (ans + sph[i]) % mod
	print(ans, end=' ')


__author__ = 'Om Kumar Sahoo'
(n, m, c) = [int(x) for x in input().split()]
u = [0] * (c + 1)
l = [0] * (c + 1)
for x in input().split():
	u[int(x)] += 1
for x in input().split():
	l[int(x)] += 1
arr = [0] * (c + 1)
for i in range(1, c + 1):
	arr[i] = u[i] * l[i]
n = len(arr)
ans = [0] * (n + 1)
ans[0] = 1
tr = [0, 1]
for i in range(n):
	ans[i + 1] = ans[i] * arr[i] % 1000000007
	j = 0
	while j < i and j < c + 2:
		ans[j + 1] = (ans[j + 1] + arr[i] * (ans[j] - arr[i] * tr[j])) % 1000000007
		j += 1
	tr = [0] + ans
for i in range(c):
	print(ans[i + 2], end=' ')