Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 to k. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen. 


-----Input-----

The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain c_{i}, the number of balls of the i-th color (1 ≤ c_{i} ≤ 1000).

The total number of balls doesn't exceed 1000.


-----Output-----

A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007. 


-----Examples-----
Input
3
2
2
1

Output
3

Input
4
1
2
3
4

Output
1680



-----Note-----

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are: 

1 2 1 2 3

1 1 2 2 3

2 1 1 2 3

Source: codeforces | Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
s = int(input())
MOD = 1000000007
MAXN = 1000
dp = [[1] + [0 for i in range(MAXN)] for j in range(MAXN + 1)]
for i in range(1, MAXN + 1):
	for j in range(1, i + 1):
		dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD
ans = 1
acum = 0
for i in range(s):
	x = int(input())
	ans = ans * dp[acum + x - 1][x - 1] % MOD
	acum += x
print(ans)


from sys import stdin, stdout
from collections import Counter
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
M = 10 ** 9 + 7
fact = [1]
for i in range(1, 1005):
	fact += [fact[-1] * i % M]

def ncr(n, r):
	num = fact[n]
	den = fact[r] * fact[n - r] % M
	ans = num * pow(den, M - 2, M) % M
	return ans
for _ in range(1):
	n = nmbr()
	a = [nmbr() for _ in range(n)]
	dp = [0] * (1 + n)
	dp[1] = 1
	spaces = 0
	sm = a[0]
	for i in range(2, n + 1):
		spaces = sm + a[i - 1] - 1
		dp[i] = dp[i - 1] * ncr(spaces, a[i - 1] - 1) % M
		sm += a[i - 1]
	print(dp[n] % M)


from sys import stdin
n = int(stdin.readline())
from math import factorial as f
lst = [int(stdin.readline()) for _ in range(n)]
summa = sum(lst)
res = 1
for (i, x) in enumerate(reversed(lst)):
	x -= 1
	summa -= 1
	res *= f(summa) // (f(summa - x) * f(x))
	res = res % 1000000007
	summa -= x
print(res)


MOD = 1000000007
fact = [1] * 1001
for i in range(1, 1001):
	fact[i] = fact[i - 1] * i
	fact[i] %= MOD

def comb(n, r):
	return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N = int(input())
List = []
for i in range(N):
	List.append(int(input()))
dp = [1] * (N + 1)
curr = 0
Ans = 1
for i in range(1, N + 1):
	Ans = Ans * comb(curr + List[i - 1] - 1, List[i - 1] - 1)
	Ans %= MOD
	curr += List[i - 1]
print(Ans)


n = int(input())
ar = [int(input()) for _ in range(n)]
for i in range(1, n):
	ar[i] += ar[i - 1]
M = 1000000007
f = [1]
for i in range(1, 1000000):
	f.append(f[-1] * i % M)

def C(n, k):
	return f[n] * pow(f[k], M - 2, M) % M * pow(f[n - k], M - 2, M) % M
dp = [1] * (n + 4)
for i in range(1, n):
	dp[i] = C(ar[i] - 1, ar[i - 1]) * dp[i - 1] % M
print(dp[n - 1])


def main():
	from math import factorial as f
	(n, res) = (0, 1)
	for _ in range(int(input())):
		m = int(input())
		res = res * f(n + m - 1) // f(n) // f(m - 1) % 1000000007
		n += m
	print(res)
main()


from math import factorial
(n, ans, s) = (int(input()), 1, 0)
for i in range(n):
	a = int(input())
	ans = ans * factorial(s + a - 1) // factorial(s) // factorial(a - 1) % 1000000007
	s += a
print(ans)


(k, mod, top) = (int(input()), 1000000007, 1000)
c = [int(input()) for _ in range(k)]
ncr = [[0] * top for _ in range(top)]
ncr[0][0] = 1
for n in range(1, top):
	ncr[n][0] = 1
	for r in range(top):
		ncr[n][r] = (ncr[n - 1][r] + ncr[n - 1][r - 1]) % mod
(ways, colors) = (1, 0)
for i in range(k):
	ways = ways * ncr[colors + c[i] - 1][c[i] - 1] % mod
	colors += c[i]
print(ways)


from math import *
from collections import deque
from copy import deepcopy
import sys

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def multi():
	return map(int, input().split())

def strmulti():
	return map(str, inp().split())

def lis():
	return list(map(int, inp().split()))

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def stringlis():
	return list(map(str, inp().split()))

def out(var):
	sys.stdout.write(str(var))

def printlist(a):
	print(' '.join((str(a[i]) for i in range(len(a)))))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
k = int(input())
ans = 1
sum = 0
for i in range(k):
	num = int(input())
	sum += num
	ans *= ncr(sum - 1, num - 1)
print(ans % 1000000007)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	N = 10001
	invfact = [0] * N
	fact = [1] * N
	for i in range(1, N):
		fact[i] = fact[i - 1] * i % mod
	invfact[-1] = pow(fact[-1], mod - 2, mod)
	for i in range(N - 2, -1, -1):
		invfact[i] = (i + 1) * invfact[i + 1] % mod

	def nCr(x, y):
		if y > x:
			return 0
		ans = invfact[x - y] * invfact[y] % mod
		ans *= fact[x]
		ans %= mod
		return ans
	k = ii()
	ans = 1
	cnt = ii()
	for i in range(1, k):
		x = ii()
		cnt += x - 1
		ans *= nCr(cnt, x - 1)
		ans %= mod
		cnt += 1
	print(ans)
if file:
	if path.exists('tmp/input.txt'):
		sys.stdin = open('tmp/input.txt', 'r')
		sys.stdout = open('tmp/output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


import sys
from functools import lru_cache
MOD = 1000000007
cnk = [[1 for i in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	for j in range(1, i):
		cnk[i][j] = cnk[i - 1][j - 1] + cnk[i - 1][j]
k = int(input())
cs = [int(input()) for i in range(k)]
ans = 1
sm = 0
for c in cs:
	sm += c
	ans = ans * cnk[sm - 1][c - 1] % MOD
print(ans)


matrix = [[0 for x in range(1001)] for y in range(1001)]
mod = 1000000007

def pascal():
	matrix[0][0] = 1
	for i in range(1001):
		for j in range(1001):
			if j == 0 or j == i:
				matrix[i][j] = 1
			else:
				matrix[i][j] = (matrix[i - 1][j - 1] + matrix[i - 1][j]) % mod
a = int(input())
b = []
for i in range(a):
	b.append(int(input()))
pascal()
r = 1
s = b[0]
for i in range(1, a):
	r = r * matrix[s + b[i] - 1][b[i] - 1] % mod
	s += b[i]
print(r)


MOD = 10 ** 9 + 7
N = 1010
f = [1 for _ in range(N)]
for i in range(1, N):
	f[i] = f[i - 1] * i % MOD
inv = [pow(f[i], MOD - 2, MOD) for i in range(N)]

def C(n, k):
	if n == 0 or k > n:
		return 0
	return f[n] * (inv[k] * inv[n - k] % MOD) % MOD
n = int(input())
tot = int(input())
ret = 1
for i in range(1, n):
	x = int(input())
	tmp = C(tot + x - 1, x - 1)
	ret = ret * tmp % MOD
	tot += x
print(ret)


k = int(input())
(res, mod, last) = (1, 10 ** 9 + 7, int(input()))
comb = [[0] * 1001 for _ in range(1001)]
comb[0][0] = 1
for i in range(1, 1001):
	comb[i][0] = 1
	for j in range(1, i + 1):
		comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod
for _ in range(k - 1):
	to_place = int(input())
	res = res * comb[last + to_place - 1][to_place - 1] % mod
	last += to_place
print(res)


numeroColores = int(input())
listaNumColores = []
for i in range(0, numeroColores):
	listaNumColores.append(int(input()))
conclusion = 1
anterior = listaNumColores[0]
for (i, numeroColores) in enumerate(listaNumColores[1:]):
	anterior += 1
	conteo1 = 1
	conteo2 = 1
	for j in range(numeroColores - 1):
		conclusion = conclusion * anterior
		anterior += 1
		conteo1 = conteo1 * conteo2
		conteo2 += 1
	conclusion = conclusion // conteo1
if conclusion > 1000000007:
	conclusion = conclusion % 1000000007
print(conclusion)


MOD = 1000000007

def C(n, k):
	global coefficients
	if k > n:
		return 0
	if k == 0 or k == n:
		return 1
	if coefficients[n][k] != -1:
		return coefficients[n][k]
	coefficients[n][k] = C(n - 1, k - 1) + C(n - 1, k)
	return coefficients[n][k] % MOD

def numberOfWays(n, K, k):
	ways = 1
	for i in range(K - 1, 0, -1):
		ways *= C(n - 1, k[i] - 1)
		ways %= MOD
		n -= k[i]
	return ways
coefficients = [[-1] * 1001 for i in range(1001)]
k = int(input())
n = 0
L = []
for i in range(k):
	L.append(int(input()))
	n += L[-1]
print(numberOfWays(n, k, L))


def fpow(a, n):
	ret = 1
	a = a % mod
	while n:
		if n & 1:
			ret = ret * a % mod
		a = a * a % mod
		n >>= 1
	return ret

def prob(i, j):
	return factorial[i] * fpow(factorial[j] * factorial[i - j] % mod, mod - 2) % mod
mod = 1000000007
sum_colors = 0
factorial = [1]
colors = []
tot = 1
for x in range(1, 1000000, 1):
	factorial.append(factorial[x - 1] * x % mod)
n_colors = int(input())
for x in range(n_colors):
	_in = int(input())
	colors.append(_in)
	sum_colors += _in
for x in range(n_colors - 1, -1, -1):
	tot = tot * prob(sum_colors - 1, colors[x] - 1) % mod
	sum_colors -= colors[x]
print(tot)


import math

def euclid_algorithm(a, b):
	(t1, t2) = (abs(a), abs(b))
	(x1, y1, x2, y2) = (int(math.copysign(1, a)), 0, 0, int(math.copysign(1, b)))
	if t1 < t2:
		(t1, t2) = (t2, t1)
		(x1, y1, x2, y2) = (x2, y2, x1, y1)
	while t2 > 0:
		if x1 * a + y1 * b != t1:
			print('inshalla')
		k = int(t1 // t2)
		(t1, t2) = (t2, t1 % t2)
		(x1, y1, x2, y2) = (x2, y2, x1 - k * x2, y1 - k * y2)
	return (t1, x1, y1)

def opposite_element(x, p):
	(gcd, k, l) = euclid_algorithm(x, p)
	if gcd != 1:
		return -1
	return k % p

def fact_mod(n, p):
	prod = 1
	for i in range(2, n + 1):
		prod *= i
		prod %= p
	return prod
k = int(input())
c = []
for i in range(k):
	c.append(int(input()))
prefix_sum = 0
p = 10 ** 9 + 7
denominator = 1
for c_i in c:
	denominator *= fact_mod(c_i - 1, p)
	denominator %= p
	prefix_sum += c_i
	denominator *= prefix_sum
	denominator %= p
numenator = fact_mod(prefix_sum, p)
print(numenator * opposite_element(denominator, p) % p)


MOD = int(1000000000.0 + 7)

def nCr(n, r):
	if 2 * r > n:
		r = n - r
	res = 1
	for i in range(r):
		res = res * (n - i) // (i + 1)
	return res
k = int(input())
n2 = int(input())
res = 1
for i in range(k - 1):
	n1 = n2
	n2 += int(input())
	res = res * nCr(n2 - 1, n1) % MOD
print(res)


s = int(input())
MOD = int(1000000000.0 + 7)
comb = [[1] + [0 for i in range(1000)] for j in range(1001)]
for i in range(1, 1001):
	for j in range(1, i + 1):
		comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD
res = 1
sums = 0
for i in range(s):
	x = int(input())
	res = res * comb[sums + x - 1][x - 1] % MOD
	sums += x
print(res)


import os
import sys
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
fact = [1] * 1002
for i in range(2, 1002):
	fact[i] = fact[i - 1] * i % mod

def ncr(n, r):
	num = fact[n]
	den = fact[n - r] * fact[r] % mod
	return num * pow(den, mod - 2, mod) % mod

def main():
	k = int(input())
	dp = [0] * (k + 1)
	dp[1] = 1
	dff = 0
	m = int(input())
	total = m
	for i in range(k - 1):
		m = int(input())
		dff = m - 1
		total += m
		dp[i + 2] = dp[i + 1] * ncr(total - 1, dff) % mod
	print(dp[k])

def nouse0():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse1():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')

def nouse2():
	a = 420
	b = 420
	print(f'i am nitish{(a + b) // 2}')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def __starting_point():
	data = [int(input()) for i in range(int(input()))]
	total = 1
	prev = data[0]
	for (i, x) in enumerate(data[1:]):
		prev += 1
		f = 1
		c = 1
		for j in range(x - 1):
			total *= prev
			prev += 1
			f *= c
			c += 1
		total //= f
		if total > 1000000007:
			total %= 1000000007
	print(total)
__starting_point()


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_right
k = int(input())
ans = 1
total = 0
MOD = 1000000007
for i in range(k):
	z = int(input())
	ans = ans * factorial(total + z - 1) // factorial(total) // factorial(z - 1) % MOD
	total += z
print(ans)


k = int(input())
mod = 10 ** 9 + 7
f = [0] * (10 ** 6 + 1)
f[0] = f[1] = 1
for i in range(2, 10 ** 6 + 1):
	f[i] = f[i - 1] * i % mod

def comb(n, r):
	return f[n] * pow(f[r], mod - 2, mod) * pow(f[n - r], mod - 2, mod) % mod
ans = 1
cc = int(input())
for i in range(1, k):
	c = int(input())
	cc += c
	ans *= comb(cc - 1, c - 1)
	ans %= mod
print(ans)


mod = 1000000007

def pow1(a, b):
	ans = 1
	c = a
	while b:
		if b & 1:
			ans = ans * c % mod
		b >>= 1
		c = c * c % mod
	return ans

def factorial(a, b):
	factor = fact[a] * pow1(fact[b] * fact[a - b] % mod, mod - 2) % mod
	return factor
fact = []
for i in range(1000010):
	fact.append(0)
a = []
for i in range(1010):
	a.append(0)
fact[0] = 1
for i in range(1, 1000000):
	fact[i] = fact[i - 1] * i % mod
n = int(input())
sum = 0
for i in range(0, n):
	a[i] = int(input())
	sum += a[i]
ans = 1
i = n - 1
while i > -1:
	ans = ans * factorial(sum - 1, a[i] - 1) % mod
	sum -= a[i]
	i -= 1
print(ans)


t = 10 ** 9 + 7
comb = [[0 for i in range(1001)] for i in range(1001)]
comb[0][0] = 1
for i in range(1, 1001):
	comb[i][0] = 1
	for j in range(1, i + 1):
		comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % t
ans = 1
f = 0
for _ in range(int(input())):
	c = int(input())
	ans = ans * comb[f + c - 1][c - 1] % t
	f += c
print(ans % t)


import math

def coloredBalls():
	k = int(input())
	if k == 1 or k == 1000:
		print('1')
		return
	n = 0
	resultado = 1
	for i in range(0, k):
		balls = int(input())
		resultado = resultado * math.factorial(n + balls - 1) // math.factorial(n) // math.factorial(balls - 1) % 1000000007
		n += balls
	print(resultado)
coloredBalls()


(k, md, s, res) = (int(input()), 1000000007, int(input()), 1)
c = [[1] + [0] * 1000 for i in range(1001)]
for i in range(1, 1001):
	for j in range(1, i + 1):
		c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % md
for i in range(1, k):
	x = int(input())
	s += x
	res = res * c[s - 1][x - 1] % md
print(res)


k = int(input())
l = [int(input()) for i in range(k)]
s = 0
ans = [0] * k
ans[0] = 1
MOD = 10 ** 9 + 7
fact = [0] * (10 ** 6 + 5)
fact[0] = 1
for i in range(1, 10 ** 6 + 5):
	fact[i] = fact[i - 1] % MOD * i % MOD % MOD

def MI(a, MOD):
	return pow(a, MOD - 2, MOD)

def c(n, k):
	if n == k or k == 0:
		return 1
	if n < k:
		return 0
	return fact[n] * MI(fact[k], MOD) % MOD * MI(fact[n - k], MOD) % MOD % MOD
ans = 1
sm = l[0]
for i in range(1, k):
	curr = l[i]
	ans = ans * c(sm + curr - 1, curr - 1)
	ans %= MOD
	sm += l[i]
print(ans)


from math import factorial
mod = 10 ** 9 + 7
k = int(input())
ans = 1
n = 0
for i in range(k):
	a = int(input())
	ans = ans * factorial(n + a - 1) // (factorial(a - 1) * factorial(n)) % mod
	n += a
print(ans)


def g():
	return int(input())

def ncr(n, r):
	if 2 * r > n:
		r = n - r
	a = 1
	for i in range(r):
		a = a * (n - i) // (i + 1)
	return a
k = g()
ans = 1
n2 = g()
for i in range(k - 1):
	n1 = n2
	n2 += g()
	ans = ans * ncr(n2 - 1, n1) % 1000000007
print(ans)


def binomialCoefficient(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res // (i + 1)
	return res
k = int(input())
sum = 0
ans = 1
m = 1000000007
for i in range(k):
	a = int(input())
	ans = ans % m * binomialCoefficient(sum + a - 1, a - 1) % m
	sum += a
print(ans)


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
k = int(input())
p = 10 ** 9 + 7
ans = 1
total = 0
for i in range(k):
	c = int(input())
	ans *= ncr(total + c - 1, total, p)
	ans %= p
	total += c
print(ans)


from sys import stdin, stdout
from collections import defaultdict
import math
mod = 10 ** 9 + 7
I = stdin.readline
P = stdout.write
k = int(I())
tot = 0
ans = 1
for i in range(k):
	now = int(I())
	ans *= math.factorial(tot + now - 1) // math.factorial(tot) // math.factorial(now - 1)
	tot += now
	ans %= mod
print(ans)


def com(lo, hi):
	loo = 1
	for i in range(1, lo + 1):
		loo *= i
	hii = 1
	for i in range(hi, hi - lo, -1):
		hii *= i
	return hii // loo
n = int(input())
data = [int(input()) for i in range(n)]
ans = 1
total = sum(data)
for i in range(len(data) - 1, -1, -1):
	ans *= com(data[i] - 1, total - 1)
	total -= data[i]
print(ans if ans < 1000000007 else ans % 1000000007)


(ans, col, mod) = (1, 0, 1000000007)
C = [[1 if i <= j else 0 for i in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	for j in range(1, i + 1):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod
for _ in range(int(input())):
	a = int(input())
	ans *= C[col + a - 1][col]
	ans %= mod
	col += a
print(ans)


from math import factorial as f
(n, ans, sm, mod) = map(int, input().split() + [1, 0, 1000000007])

def ncr(x, y):
	return f(x) // (f(y) * f(x - y))
for _ in range(n):
	x = int(input())
	ans = ans * ncr(sm + x - 1, x - 1) % mod
	sm += x
print(ans)


kk = 1
f = [0] * 1001
f[0] = 1
for i in range(1, 1001):
	kk *= i
	kk %= 10 ** 9 + 7
	f[i] = pow(kk, 10 ** 9 + 5, 10 ** 9 + 7)

def c(n, k):
	prod = 1
	for i in range(n - k + 1, n + 1):
		prod *= i
		prod %= 10 ** 9 + 7
	prod = prod * f[k] % (10 ** 9 + 7)
	return prod
l = []
m = []
a = 1
s = 0
for i in range(int(input())):
	x = int(input())
	s += x
	l.append(s - 1)
	m.append(x - 1)
ans = 1
for i in range(len(l)):
	ans = ans * c(l[i], m[i]) % (10 ** 9 + 7)
print(ans)


pt = []
for i in range(1000):
	pt.append([0] * (i + 1))
	pt[i][0] = pt[i][i] = 1
	for j in range(1, i):
		pt[i][j] = pt[i - 1][j - 1] + pt[i - 1][j]
(k, s, v) = (int(input()), int(input()), 1)
for i in range(1, k):
	c = int(input())
	v = v * pt[s + c - 1][c - 1] % 1000000007
	s += c
print(v)


nCr = [[0 for i in range(1001)] for j in range(1001)]
nCr[0][0] = 1
for i in range(1, 1001):
	nCr[i][0] = 1
	for j in range(1, i + 1):
		nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % 1000000007
n = int(input())
data = []
for i in range(n):
	data.append(int(input()))
ans = 1
total = 0
for i in range(n):
	ans = ans * nCr[total + data[i] - 1][data[i] - 1] % 1000000007
	total += data[i]
print(int(ans))


from math import factorial
(k, s, res) = (int(input()), int(input()), 1)
for i in range(1, k):
	x = int(input())
	s += x
	res = res * factorial(s - 1) // factorial(x - 1) // factorial(s - x) % 1000000007
print(res)


from math import factorial as f
n = int(input())
d = 0
out = 1
for i in range(n):
	m = int(input())
	out = out * f(d + m - 1) // f(d) // f(m - 1) % 1000000007
	d += m
print(out)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def nCr_mod(n, r, max_n=2 * 10 ** 5, mod=10 ** 9 + 7):
	max_n = min(max_n, mod - 1)
	(fact, inv_fact) = ([0] * (max_n + 1), [0] * (max_n + 1))
	fact[0] = 1
	for i in range(max_n):
		fact[i + 1] = fact[i] * (i + 1) % mod
	inv_fact[-1] = pow(fact[-1], mod - 2, mod)
	for i in reversed(range(max_n)):
		inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

	def do_nCr_mod(n, r):
		res = 1
		while n or r:
			(a, b) = (n % mod, r % mod)
			if a < b:
				return 0
			res = res * fact[a] % mod * inv_fact[b] % mod * inv_fact[a - b] % mod
			n //= mod
			r //= mod
		return res
	return do_nCr_mod(n, r)

def solve(case):
	n = int(inp())
	ans = 1
	total = 0
	for i in range(n):
		x = int(inp())
		total += x
		ans *= ncr(total - 1, x - 1) % mod
	print(ans % mod)
testcase(1)


import sys
input = sys.stdin.readline
MAX = 1010
MOD = 10 ** 9 + 7
fact = [0] * MAX
inv = [0] * MAX
finv = [0] * MAX
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
	fact[i] = fact[i - 1] * i % MOD
	inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def C(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fact[n] * (finv[r] * finv[n - r] % MOD) % MOD
k = int(input())
c = [int(input()) for _ in range(k)]
s = sum(c)
acc = 0
p = [0] * (s + 1)
p[0] = 1
for ci in c:
	np = [0] * (s + 1)
	p_acc = p[0]
	for i in range(1, s + 1):
		np[i] = p_acc * C(i - acc - 1, ci - 1) % MOD
		p_acc += p[i]
	acc += ci
	p = np
print(p[s])


k = int(input())
(nax, m) = (1005, 1000000007)
c = [[[0, 1][j == 0] for j in range(nax)] for i in range(nax)]
for i in range(1, nax):
	for j in range(1, nax):
		c[i][j] = c[i - 1][j] + c[i - 1][j - 1]
(ans, pref) = (1, [-1])
for i in range(k):
	a = int(input())
	pref.append(pref[-1] + a)
	ans *= c[pref[-1]][a - 1]
	ans %= m
print(ans)


from math import factorial as f

def ncr(n, r):
	return f(n) // (f(r) * f(n - r))
k = int(input())
k += -1
ans = 1
t1 = int(input())
while k:
	k += -1
	t2 = int(input())
	ans *= ncr(t1 + t2 - 1, t2 - 1)
	t1 += t2
print(ans % 1000000007)


c = []
k = int(input())
for i in range(k):
	c.append(int(input()))
maxN = 1010
binomials = [[1], [1, 1]]
for i in range(2, maxN):
	binomials.append([1])
	for j in range(1, i):
		binomials[i].append((binomials[i - 1][j - 1] + binomials[i - 1][j]) % 1000000007)
	binomials[i].append(1)
dp = [1] * k
for i in range(1, k):
	dp[i] = dp[i - 1] * binomials[sum(c[:i + 1]) - 1][c[i] - 1] % 1000000007
print(dp[k - 1])


import math as ma
m = 10 ** 9 + 7
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
b = a[0]
c = 1
for i in range(1, n):
	c = c * (ma.factorial(b + a[i] - 1) // (ma.factorial(b) * ma.factorial(a[i] - 1))) % m
	b = (b + a[i]) % m
print(c)


from sys import stdin
from collections import deque
mod = 10 ** 9 + 7
import sys
from queue import PriorityQueue
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
import heapq
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
from itertools import permutations
from math import factorial as f

def ncr(x, y):
	return f(x) // (f(y) * f(x - y))
n = int(input())
ans = 1
sm = 0
for _ in range(n):
	x = int(input())
	ans = ans * ncr(sm + x - 1, x - 1) % mod
	sm += x
print(ans)


def f(a, b):
	p = 1
	while a != b:
		p = p * a % z
		a -= 1
	return p

def modinv(a, m):
	p = 1
	while m != 0:
		if m % 2:
			p = p * a % z
			m -= 1
		else:
			a = a * a % z
			m //= 2
	return p
k = int(input())
s = 0
ans = 1
z = 1000000007
for i in range(k):
	c = int(input())
	if i > 0:
		ans = ans * f(s + c - 1, c - 1) * modinv(f(s, 0), z - 2) % z
	s += c
print(ans)


(ans, s) = (1, 0)
for _ in range(int(input())):
	n = int(input())
	s += n
	if s == n:
		continue
	k = 1
	for i in range(1, n):
		k = k * (s - i) // i
	ans = ans * k % (10 ** 9 + 7)
print(ans)


from math import factorial
k = int(input())
(ans, s) = (1, 0)
for i in range(k):
	ci = int(input())
	ans = ans * factorial(s + ci - 1) // (factorial(ci - 1) * factorial(s)) % 1000000007
	s += ci
print(ans)


import math

def read_data():
	k = int(input())
	ns = [int(input()) for i in range(k)]
	return (k, ns)

def solve(k, ns):
	n = sum(ns)
	free_pos = n
	result = 1
	mod = 10 ** 9 + 7
	for ni in reversed(ns):
		tmp = math.factorial(free_pos - 1) // math.factorial(free_pos - ni)
		tmp //= math.factorial(ni - 1)
		tmp %= mod
		result *= tmp
		result %= mod
		free_pos -= ni
	return result
(k, ns) = read_data()
print(solve(k, ns))


k = int(input())
c = [int(input()) for i in range(k)]
(mod, ans, s) = (1000000007, 1, 0)
ri = [0, 1]
for i in range(2, 1000010):
	ri.append(mod // i * (mod - ri[mod % i]) % mod)
for p in c:
	for i in range(1, p):
		ans = ans * (s + i) * ri[i] % mod
	s += p
print(ans)


k = int(input())
a = []
for _ in range(k):
	a.append(int(input()))
n = sum(a)
N = 1000000007

def getCombi(a, n):
	b = min(a, n - a)
	ret = 1
	for i in range(1, b + 1):
		ret = ret * (n + 1 - i) // i
	return ret % N
ret = 1
for i in range(k - 1, 0, -1):
	ai = a[i] - 1
	ni = sum(a[:i])
	ret *= getCombi(ai, ni + ai)
	ret %= N
print(ret)


from functools import reduce
from operator import mul
mod = 10 ** 9 + 7
k = int(input())
cs = [int(input()) for _ in range(k)]
cumcs = cs[:]
for i in range(1, len(cs)):
	cumcs[i] += cumcs[i - 1]

def C(n, k):
	num = reduce(mul, range(n, n - k, -1), 1)
	denom = reduce(mul, range(k, 0, -1), 1)
	return num // denom % mod
res = 1
for (cum, c) in zip(cumcs, cs):
	res = res * C(cum - 1, c - 1) % mod
print(res)


from heapq import heapify, heappush, heappop
from collections import Counter, defaultdict, deque, OrderedDict
from sys import setrecursionlimit, maxsize
from bisect import bisect_left, bisect, insort_left, insort
from math import ceil, log, factorial, hypot, pi
from fractions import gcd
from copy import deepcopy
from functools import reduce
from operator import mul
from itertools import product, permutations, combinations, accumulate, cycle
from string import ascii_uppercase, ascii_lowercase, ascii_letters, digits, hexdigits, octdigits
prod = lambda l: reduce(mul, l)
prodmod = lambda l, mod: reduce(lambda x, y: mul(x, y) % mod, l)

def read_list(t):
	return [t(x) for x in input().split()]

def read_line(t):
	return t(input())

def read_lines(t, N):
	return [t(input()) for _ in range(N)]
mod = 10 ** 9 + 7

def inv(x):
	return pow(x, mod - 2, mod)
K = read_line(int)
balls = read_lines(int, K)
s = balls[0]
ans = 1
for ball in balls[1:]:
	ans *= ball
	ans %= mod
	for i in range(s + 1, s + ball):
		ans *= i
		ans %= mod
	for i in range(ball):
		ans *= inv(i + 1)
		ans %= mod
	s += ball
print(ans)


def main():
	MOD = int(1000000000.0 + 7)

	def power(x, p):
		if p == 0:
			return 1
		if p & 1:
			return x * power(x, p - 1) % MOD
		return power(x * x % MOD, p >> 1) % MOD
	import sys
	(k, *c) = [int(i) for i in sys.stdin.read().split()]
	inv_factorial = [1] * 1001
	factorial = [1] * 1001
	for i in range(2, 1001):
		factorial[i] = factorial[i - 1] * i % MOD
		inv_factorial[i] = power(factorial[i], MOD - 2)
	result = 1
	size = 0
	for i in c:
		size += i
		m = factorial[size - 1] * inv_factorial[i - 1] % MOD * inv_factorial[size - i] % MOD
		result = result * m % MOD
	print(result)
main()


mx = 1001
mod = 1000000007
nCr = [[0 for i in range(mx)] for j in range(mx)]
nCr[0][0] = 1
for i in range(1, mx):
	nCr[i][0] = 1
	for j in range(1, mx):
		nCr[i][j] = nCr[i - 1][j - 1] + nCr[i - 1][j]
n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
res = 1
total = 0
for i in range(n):
	res = res * nCr[total + l[i] - 1][l[i] - 1] % mod
	total += l[i]
print(res)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

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

def lcm(a, b):
	return a / gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 0
	right = len(a)
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = lint()
	return n
d = defaultdict(lambda : [])

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1
n = I()
s = [I() for _ in range(n)]
ans = 1
tot = s[0]
for i in range(1, n):
	tot += s[i]
	ans *= nCr(tot - 1, s[i] - 1)
print(ans % mod)


k = int(input())
h = []
for i in range(k):
	h.append(int(input()))
ffs = [1]

def f(n):
	if n < len(ffs):
		return ffs[n]
	v = n * f(n - 1)
	ffs.append(v)
	return v

def c(k, n):
	return f(n) // (f(k) * f(n - k))

def cc(k, n):
	return c(n - 1, n + k - 1)

def solve(h):
	if len(h) == 1:
		return 1
	hh = h[:-1]
	hh_len = sum(hh)
	return solve(hh) * cc(h[-1] - 1, hh_len + 1)
r = 1
for i in range(len(h)):
	r *= cc(h[i] - 1, sum(h[:i]) + 1)
print(r % 1000000007)


mod = 10 ** 9 + 7
k = int(input())
maxi = 1001
arr = []
for i in range(k):
	arr.append(int(input()))
C = [[0 for i in range(maxi)] for i in range(maxi)]
for i in range(maxi):
	for j in range(i + 1):
		if i == j:
			C[i][j] = 1
		else:
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
ans = 1
tot = arr[0]
for i in arr[1:]:
	tot += i
	ans = ans * C[tot - 1][i - 1] % mod
print(ans % mod)


MOD = 1000000007
MAX_BALLS = 1000

def initFactors():
	factors = [1]
	for i in range(1, MAX_BALLS + 1):
		last_fact = factors[-1]
		factors.append(last_fact * i)
	return factors
n_colors = int(input())
factors = initFactors()
balls = []
for i in range(n_colors):
	balls.append(int(input()))
res = 1
l = balls[0]
for i in range(1, n_colors):
	res *= factors[l + balls[i] - 1] // (factors[l] * factors[balls[i] - 1]) % MOD
	l += balls[i]
print(res % MOD)


mod = 1000000007

def C(n, r):
	if r > n - r:
		r = n - r
	val = 1
	for i in range(1, r + 1):
		val *= n - r + i
		val //= i
	return val % mod
n = int(input())
a = []
for _ in range(n):
	a.append(int(input()))
z = [0 for _ in range(n)]
cum = 0
val = 1
for i in range(n):
	cum += a[i]
	val *= C(cum - 1, a[i] - 1)
	val %= mod
print(val)