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 ci, the number of balls of the i-th color (1 ≤ ci ≤ 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

Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
from sys import stdin
c = [[0] * 1002 for _ in range(0, 1002)]
MOD = int(1000000000.0 + 7)
for i in range(0, 1002):
	c[i][0] = c[i][i] = 1
	for j in range(0, i):
		c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD
r = map(int, stdin.read().split())
n = next(r)
ans = 1
sum = 0
for _ in range(0, n):
	x = next(r)
	ans = ans * c[sum + x - 1][sum] % MOD
	sum += x
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
(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)


mod = 10 ** 9 + 7
import math

def f(n):
	return math.factorial(n)
k = int(input())
c = [int(input()) for i in range(k)]
(s, cnt) = (0, 1)
for i in c:
	cnt *= f(s + i - 1) // f(i - 1) // f(s)
	cnt %= mod
	s += i
print(cnt)


import sys
import inspect
import re
import math
from pprint import pprint as pp
mod = 1000000007
MAX = 10 ** 15

def deb(p):
	for line in inspect.getframeinfo(inspect.currentframe().f_back)[3]:
		m = re.search('\\bdeb\\s*\\(\\s*([A-Za-z_][A-Za-z0-9_]*)\\s*\\)', line)
		print('%s %d' % (m.group(1), p))

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat

def pascle(lim):
	p = matrix(lim, lim)
	for i in range(lim):
		p[i][i] = p[i][0] = 1
	for i in range(1, lim):
		for j in range(1, lim):
			p[i][j] = (p[i - 1][j - 1] + p[i - 1][j]) % mod
	return p

def main():
	p = pascle(1005)
	n = int(input())
	a = [0] + [int(input()) for i in range(n)]
	s = 0
	ans = 1
	for i in range(1, n + 1):
		ans = ans * p[s + a[i] - 1][a[i] - 1] % mod
		s += a[i]
	print(ans)
main()


k = int(input())
fact = [1] * 1000000
for j in range(2, 1001):
	fact[j] = fact[j - 1] * j
cnt = 1
l = 0
for i in range(k):
	cur = int(input())
	cnt *= fact[l + cur - 1] // fact[cur - 1] // fact[l] % 1000000007
	l += cur
print(int(cnt) % 1000000007)


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)


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)


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)


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()


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)


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])


k = int(input())
sol = 1
prije = 0
for i in range(k):
	color = int(input())
	br1 = 1
	for y in range(prije + 1, prije + color):
		br1 *= y
	br2 = 1
	for y in range(color - 1, 1, -1):
		br2 *= y
	prije += color
	sol *= br1 // br2
	sol %= 10 ** 9 + 7
print(sol)


def comb(x, y):
	num = 1
	for i in range(x - y + 1, x + 1):
		num *= i
	den = 1
	for i in range(1, y + 1):
		den *= i
	return num // den
n_colors = int(input())
balls = []
for _ in range(n_colors):
	balls.append(int(input()))
total = 1
for i in range(len(balls) - 1, 0, -1):
	total *= comb(sum(balls[:i + 1]) - 1, balls[i] - 1) % 1000000007
	total %= 1000000007
print(total)


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)


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)


fact = [1]
mod = 1000000007
for j in range(1, 1001):
	fact.append(fact[-1] * j)
a = int(input())
s = []
for i in range(a):
	s.append(int(input()))
summ = 1
l = s[0]
for i in range(1, a):
	summ *= fact[l + s[i] - 1] // fact[l] // fact[s[i] - 1] % mod
	l += s[i]
print(summ % mod)


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 sys

def choose(n, k):
	if 0 <= k <= n:
		ntok = 1
		ktok = 1
		for t in range(1, min(k, n - k) + 1):
			ntok *= n
			ktok *= t
			n -= 1
		return ntok // ktok
	else:
		return 0
R = 1000000007

def main():
	k = int(sys.stdin.readline())
	data = list(map(int, sys.stdin.readlines()))
	s = sum(data)
	ans = 1
	free = s
	for i in range(k - 1, 0, -1):
		t = choose(free - 1, data[i] - 1)
		ans = t % R * ans % R
		free -= data[i]
	print(ans)
main()


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)


import math
MOD = 1000000007
MAXN = 1005
comb = [[0] * MAXN for i in range(0, MAXN)]
comb[0][0] = 1
for i in range(1, MAXN):
	comb[i][0] = 1
	for j in range(1, i + 1):
		comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]
		comb[i][j] %= MOD
k = int(input())
sum = 0
ans = 1
for i in range(0, k):
	num = int(input())
	sum += num
	ans = ans * comb[sum - 1][num - 1] % MOD
print(ans)


MOD = 10 ** 9 + 7

def fact(n):
	factor = 1
	if n == 0:
		return 1
	for i in range(1, n + 1):
		factor = factor * i
	return factor
mass = []
n = int(input())
for i in range(n):
	mass.append(int(input()))
res = 1
summ = 0
for i in range(n):
	summ += mass[i]
	res = res * fact(summ - 1) // (fact(mass[i] - 1) * fact(summ - mass[i])) % MOD
print(res)


import sys
import math
from math import *
from operator import add
from itertools import permutations
import itertools
inf = 10000000000.0
mod = int(1000000000.0 + 7)

def NcR(n, r):
	p = 1
	k = 1
	if n - r < r:
		r = n - r
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	return p
t = 1
for _ in range(t):
	k = int(input())
	total = int(input())
	res = 1
	for i in range(1, k):
		c = int(input())
		res = res * NcR(total + c - 1, c - 1) % mod
		total += c
	print(res)


def C(n, k):
	return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
import sys
import math
sys.setrecursionlimit(5000)
n = int(input())
arr = [0]
for i in range(n):
	arr.append(int(input()))
sum = [0] * (n + 1)
ans = 1
for i in range(1, n + 1):
	sum[i] = sum[i - 1] + arr[i - 1]
for i in range(1, n + 1):
	if arr[i] > 1:
		ans *= C(sum[i] + arr[i] - 1, sum[i])
print(ans % 1000000007)


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)


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


INF = 1000000007
k = int(input())
ks = []
for i in range(k):
	ks.append(int(input()))
facts = [1, 1]
for i in range(2, 1000):
	facts.append(facts[i - 1] * i)
count = 1
summ = ks[0]
for i in range(1, k):
	count *= facts[ks[i] - 1 + summ] // facts[summ] // facts[ks[i] - 1]
	count %= INF
	summ += ks[i]
print(count % INF)


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))


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)


n = int(input())
cnt = []
for i in range(n):
	cnt.append(int(input()))
dp = [1]
length = [cnt[0]]
MOD = int(1000000007)

def C(n, k):
	assert n >= k
	res = 1
	for i in range(n - k + 1, n + 1):
		res *= i
	for i in range(2, k + 1):
		res //= i
	return res % MOD
for i in range(1, n):
	length.append(length[i - 1] + cnt[i])
	dp.append(dp[i - 1] * C(length[i] - 1, cnt[i] - 1) % MOD)
print(dp[n - 1])


def fact(x):
	r = 1
	for i in range(1, x + 1):
		r *= i
	return r
mod = int(1000000000.0 + 7)
n = int(input())
arr = [0] * n
for i in range(n):
	arr[i] = int(input())
r = 1
s = 0
for i in range(1, n):
	s += arr[i - 1]
	r *= fact(s + arr[i] - 1) // fact(s) // fact(arr[i] - 1)
	r %= mod
print(r)


def fact(n):
	p = n
	for i in range(1, n):
		p *= i
	if n == 0:
		return 1
	return p

def ncr(n, r):
	return fact(n) // fact(n - r) // fact(r)
n = int(input())
c = []
for i in range(n):
	k = int(input())
	c.insert(len(c), k)
p = 1
sum = 0
for i in range(n):
	sum += c[i]
for i in range(n, 0, -1):
	p = p * ncr(sum - 1, c[i - 1] - 1)
	p %= 1000000007
	sum -= c[i - 1]
print(int(p))


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)


(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)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7
facs = [1]
curr = 1
for j in range(1, 10 ** 6 + 1):
	curr *= j
	curr %= MOD
	facs.append(curr)

def solve():
	N = getInt()
	cols = []
	pref = []
	curr = 0
	for i in range(N):
		x = getInt()
		curr += x
		cols.append(x)
		pref.append(curr)
	dp = 1
	for j in range(1, N):
		tot = pref[j]
		mult = facs[tot - 1] * pow(facs[cols[j] - 1], MOD - 2, MOD) * pow(facs[pref[j - 1]], MOD - 2, MOD)
		dp *= mult
		dp %= MOD
	return dp
print(solve())


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)


ans = 1
n = int(input())
s = int(input())
mod = 1000000007
for _ in range(1, n):
	now = int(input())
	s += now
	k = 1
	for i in range(now - 1):
		k = k * (s - 1 - i) // (i + 1)
	ans = ans * k % mod
print(ans)


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])


def c(k, l):
	d = 1
	for i in range(k + 1, l + k + 1):
		d *= i
	for i in range(l):
		d //= i + 1
	return d % 1000000007
ans = 1
n = int(input())
k = int(input())
for t in range(1, n):
	a = int(input())
	ans *= c(k, a - 1) % 1000000007
	k += a
print(ans % 1000000007)


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()


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)


import os
import sys
from collections import *
from fractions import *
from bisect import *
from heapq import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 1000000007
EPS = 1e-06

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def nCr(n, r, p=M):
	num = 1
	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()
c = []
for i in range(k):
	c.append(Int())
have_spaces = 0
ans = 1
for i in range(k):
	have_spaces += c[i]
	possible = nCr(have_spaces - 1, c[i] - 1)
	ans = ans * possible % M
print(ans)


__author__ = 'taras-sereda'
from pprint import pprint as pp
n = int(input())
maxn = 1000
mod = 1000000007
coef = [[0 for i in range(maxn)] for i in range(maxn)]
for i in range(maxn):
	coef[i][0] = 1
	for j in range(1, maxn):
		coef[i][j] = (coef[i - 1][j] + coef[i - 1][j - 1]) % mod
colors = [int(input()) for i in range(n)]
res = 1
total = 0
for i in range(n):
	res = res * coef[total + colors[i] - 1][colors[i] - 1] % mod
	total += colors[i]
print(res)


pc = c = 0
res = 1
for i in range(int(input())):
	pc += c
	c = int(input())
	for k in range(1, c):
		res = res * (pc + c - k) // k
	res %= 1000000007
print(res)


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)


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)


MOD = 10 ** 9 + 7
import os
import math

def combination(n, k):
	return math.factorial(n) // math.factorial(k) // math.factorial(n - k) % MOD

def main():
	k = int(input().strip())
	a = []
	for i in range(k):
		a.append(int(input().strip()))
	dp = [1]
	used = a[0]
	for i in range(1, k):
		used += a[i]
		dp.append(dp[i - 1] * combination(used - 1, a[i] - 1) % MOD)
	print(dp[-1])
main()


k = int(input())
l = [int(input()) for i in range(k)]
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)


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)


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)


(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)


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])


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)


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)


from math import factorial
n = int(input())
c = [int(input()) for _ in range(n)]
(r, s) = (1, 0)
for i in range(n):
	r *= factorial(s + c[i] - 1) // factorial(s) // factorial(c[i] - 1)
	r %= 1000000007
	s += c[i]
print(r)


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)


from math import *
n = int(input())
k1 = int(input())
last_vars = 1
num_pos = k1
for i in range(n - 1):
	ki = int(input())
	num_pos += ki
	ki -= 1
	Cnk = 1
	for k in range(num_pos - ki, num_pos):
		Cnk *= k
	Cnk //= factorial(ki)
	last_vars *= Cnk
print(last_vars % 1000000007)


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()


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)


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 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 = int(1000000000.0 + 7)
C = [[0] * 1001 for i in range(1001)]
C[0][0] = 1
for n in range(1, 1001):
	C[n][0] = 1
	C[n][n] = 1
	for k in range(1, n):
		C[n][k] = C[n - 1][k - 1] + C[n - 1][k]
k = int(input())
r = 1
n = 0
for i in range(k):
	c = int(input())
	n += c
	r = r * C[n - 1][c - 1] % MOD
print(r)


f = [1] * 10 ** 6
for i in range(2, 10 ** 3 + 1):
	f[i] = f[i - 1] * i
k = int(input())
s = 0
ans = 1
for i in range(k):
	c = int(input())
	ans *= f[s + c - 1] // f[c - 1] // f[s] % (10 ** 9 + 7)
	s += c
print(ans % (10 ** 9 + 7))


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)


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)


n = int(input())
ret = 1
sum = 0
mod = 1000000007
for a in range(n):
	q = int(input())
	e = 1
	for b in range(q - 1):
		e *= sum + 1 + b
	sil = 1
	for b in range(2, q):
		sil *= b
	e //= sil
	e %= mod
	ret *= e
	ret %= mod
	sum += q
print(ret)


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)


ans = 1
prev = 0
M = 10 ** 9 + 7
for _ in range(int(input())):
	x = int(input())
	prev += x
	if _ == 0:
		continue
	a = 1
	for i in range(1, x):
		a = a * (prev - i) // i
	ans = ans * a % M
print(ans)


def color(arr):
	s = 0
	ans = 1
	for i in arr:
		temp = 1
		s += i
		if s == i:
			continue
		for placement in range(1, i):
			temp = temp * (s - placement) // placement
		ans *= temp % (10 ** 9 + 7)
	return ans % (10 ** 9 + 7)
blanck = []
for i in range(int(input())):
	blanck.append(int(input()))
print(color(blanck))


def fact(x):
	res = 1
	while x > 0:
		res *= x
		x -= 1
	return res
k = int(input())
lst = []
for i in range(0, k):
	x = int(input())
	lst.append(x)
l = lst[0]
ans = 1
for i in range(1, k):
	l += lst[i] - 1
	ans *= fact(l) // (fact(l - lst[i] + 1) * fact(lst[i] - 1))
	l += 1
print(ans % (1000 * 1000 * 1000 + 7))


import unittest
import sys
import re

class Colored:
	MOD = 1000000007

	def __init__(self, args):
		self.list = args

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

	def binom(self, n, k):
		return self.fact(n) // (self.fact(n - k) * self.fact(k))

	def f(self, i):
		if i == 0:
			return 1
		bin = self.binom(sum(self.list[:i + 1]) - 1, self.list[i] - 1)
		return bin % self.MOD * self.f(i - 1)

	def calculate(self):
		result = self.f(len(self.list) - 1) % self.MOD
		return str(result)

def get_inputs(test_inputs=None):
	it = iter(test_inputs.split('\n')) if test_inputs else None

	def uinput():
		if it:
			return next(it)
		else:
			return input()
	num = int(uinput())
	nums = [int(uinput()) for i in range(num)]
	inputs = nums
	return inputs

def calculate(test_inputs=None):
	return Colored(get_inputs(test_inputs)).calculate()

class unitTests(unittest.TestCase):

	def test_sample_tests(self):
		self.assertEqual(calculate('3\n2\n2\n1'), '3')
		self.assertEqual(calculate('4\n1\n2\n3\n4'), '1680')
		self.assertEqual(calculate('10\n100\n100\n100\n100\n100\n100\n100' + '\n100\n100\n100'), '12520708')
		s = '1000'
		for n in range(1000):
			s += '\n1'
		self.assertEqual(calculate(s), '1')

	def test_get_inputs(self):
		self.assertEqual(get_inputs('2\n1\n3'), [1, 3])

	def test_Colored_class__basic_functions(self):
		d = Colored([2, 1])
		self.assertEqual(d.list, [2, 1])
		self.assertEqual(d.fact(4), 24)
		self.assertEqual(d.binom(2, 1), 2)
		self.assertEqual(d.f(0), 1)
		self.assertEqual(d.f(1), 1)
sys.setrecursionlimit(10000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
print(calculate())


import sys
import math
import collections
from pprint import pprint
mod = 1000000007

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat

def pascle(lim):
	p = matrix(lim, lim)
	for i in range(lim):
		p[i][i] = p[i][0] = 1
	for i in range(1, lim):
		for j in range(1, lim):
			p[i][j] = (p[i - 1][j - 1] + p[i - 1][j]) % mod
	return p
p = pascle(1005)
n = int(input())
a = [0] + [int(input()) for i in range(n)]
s = 0
ans = 1
for i in range(1, n + 1):
	ans = ans * p[s + a[i] - 1][a[i] - 1] % mod
	s += a[i]
print(ans)


fac = [1] * 1001
for i in range(1, 1001):
	fac[i] = fac[i - 1] * i
k = int(input())
tmp = 0
res = 1
for i in range(k):
	tmp2 = int(input())
	res *= fac[tmp2 + tmp - 1] // fac[tmp2 - 1] // fac[tmp] % (10 ** 9 + 7)
	tmp += tmp2
print(res % (10 ** 9 + 7))


import sys
input = sys.stdin.readline
p = 10 ** 9 + 7
pri = p
fac = [1 for i in range(10 ** 6 + 1)]
for i in range(2, len(fac)):
	fac[i] = fac[i - 1] * (i % pri) % pri

def modi(x):
	return pow(x, p - 2, p) % p

def ncr(n, r):
	x = fac[n] * (modi(fac[r]) % p * (modi(fac[n - r]) % p)) % p % p
	return x
a = int(input())
ans = [0 for i in range(a + 1)]
for i in range(a):
	s = int(input())
	ans[i + 1] = s
pref = [0]
for i in range(1, a + 1):
	pref.append(pref[-1] + ans[i])
total = 1
for i in range(2, len(ans)):
	spaces = pref[i - 1] + 1
	items = ans[i] - 1
	x = ncr(spaces + items - 1, spaces - 1)
	x %= pri
	total = total * x % pri
print(total)


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)


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)


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 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)


def fact(n):
	r = 1
	for i in range(1, n + 1):
		r *= i
	return r
n = int(input())
c = [int(input()) for i in range(n)]
r = 1
u = c[0] - 1
d = 0
for i in range(1, n):
	u += c[i]
	d += c[i - 1]
	r *= fact(u) // fact(d) // fact(c[i] - 1)
print(r % 1000000007)


k = int(input())
c = [int(input()) for _ in range(k)]
MOD = 10 ** 9 + 7

def fact(x):
	prod = 1
	for i in range(1, x + 1):
		prod *= i
	return prod

def C(n, k):
	prod = 1
	for i in range(n - k + 1, n + 1):
		prod *= i
	return prod // fact(k) % MOD
prod = 1
c_sum = -1
for c_i in c:
	c_sum += c_i
	prod *= C(c_sum, c_i - 1)
	prod %= MOD
print(prod)


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)


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)


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)


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)


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)


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)


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 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()


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 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)


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)


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 = 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)


n = int(input())
a = [0]
s = [0]
md = 1000000007
for i in range(n):
	x = int(input())
	a.append(x)
	s.append(s[len(s) - 1] + x)

def factor(x):
	total = 1
	for i in range(2, x + 1):
		total *= i
	return total
ans = 1
for i in range(2, n + 1):
	ans *= factor(s[i - 1] + a[i] - 1) // factor(s[i - 1]) // factor(a[i] - 1)
	ans %= md
print(ans)


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)


n = int(input())
balls = []
for i in range(n):
	balls.append(int(input()))
ans = 1
urns = balls[0] + 1

def theorem(n, k):
	ret = 1
	for i in range(1, k + 1):
		ret = ret * (n + k - i)
	for i in range(1, k + 1):
		ret = ret // i
	return ret
for i in range(1, n):
	ans *= theorem(urns, balls[i] - 1) % 1000000007
	urns += balls[i]
print(ans % 1000000007)


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)


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)


MOD = 1000000007
k = int(input())
c = [int(input()) for i in range(k)]
total_c = sum(c)
comb = [[0] * (max(c) + 1) for i in range(total_c + 1)]
comb[0][0] = 1
for i in range(1, len(comb)):
	comb[i][0] = 1
	for j in range(1, len(comb[0])):
		comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]
		comb[i][j] %= MOD
w = [0] * (total_c + 1)
w[0] = 1
for color in range(k):
	new_w = [0] * len(w)
	for n in range(len(new_w)):
		new_w[n] = w[n]
		for i in range(c[color]):
			if n - i - 1 < 0:
				break
			new_w[n] += comb[n - 1][i] * w[n - i - 1]
			new_w[n] %= MOD
	w = new_w
print(w[total_c])


n = 1000
mod = 10 ** 9 + 7
pascal = [[1]]
for r in range(1, n + 1):
	previous_row = pascal[-1]
	row = [1]
	for c in range(1, r):
		row.append((previous_row[c - 1] + previous_row[c]) % mod)
	row.append(1)
	pascal.append(row)
k = int(input())
length = int(input())
product = 1
for i in range(1, k):
	curr = int(input())
	product *= pascal[length + curr - 1][length]
	product %= mod
	length += curr
print(product)


(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 exp

def pfold(arr):
	return arr[0] * pfold(arr[1:]) if arr else 1

def pscan(x, arr):
	arr = pscan(x * arr[-1], arr[:-1]) if arr else []
	arr.append(x)
	return arr

def P(n, r):
	return pfold(range(n, n - r, -1))

def F(n):
	return P(n, n)

def C(n, r):
	if r > n:
		return 0
	r = min(r, n - r)
	return P(n, r) // F(r)

def AC(a, b):
	return C(a + b - 1, b - 1)

def CCC(n, k):
	return AC(n, k) / F(k)

def Cat(n):
	return C(2 * n, n + 1) / n

def Cat2(n):
	return

def dot(a, b):
	return sum((i * j for (i, j) in zip(a, b)))

def Catray(n):
	arr = [1]
	for i in range(1, n):
		arr = arr + [dot(arr, arr[::-1])]
	return arr

def Bd(n, p, k):
	return C(n, k) * p ** k * (1 - p) ** (n - k)

def BdS(n, p, k):
	return sum((Bd(n, p, i) for i in range(k + 1)))

def Normal(mu, sigma, k):
	return 0

def Ed(p, k):
	return (1 - p) * p ** (k - 1)

def EdS(p, k):
	return 1 - p ** k

def Pd(x, k):
	return x ** k / F(k) * exp(-x)

def PdS(x, k):
	return sum(pscan(1, [x / i for i in range(k, 0, -1)])) * exp(-x)

def nTermsSumToXInRangeAToB(n, x, a, b):
	x -= a * n
	b -= a
	if x < 0 or x > b * n:
		return 0
	else:
		return nTermsUnderASumToX(n, x, b + 1, 0)

def nTermsUnderASumToX(n, x, a, b):
	if x < 0:
		return 0
	else:
		return AC(x, n) - (n - b) * nTermsUnderASumToX(n, x - a, a, b + 1)

def f(n, x, a, b):
	return nTermsSumToXInRangeAToB(n, x, a, b)
M = 10 ** 9 + 7
k = int(input())
v = 1
n = 0
for _ in range(k):
	c = int(input())
	v *= C(n + c - 1, c - 1)
	v %= M
	n += c
print(v)


import math
MOD = 1000000007
MAXN = 1005

def fac(n, k):
	res = 1
	for i in range(n + 1 - k, n + 1):
		res *= i
	return res
k = int(input())
sum = 0
ans = 1
for i in range(0, k):
	num = int(input())
	sum += num
	ans = ans * fac(sum - 1, num - 1) // fac(num - 1, num - 1)
print(ans % MOD)


import itertools as it
import functools
import operator
import collections
import math
import sys
LARGE_NUMBER = 1000000007

@functools.lru_cache(maxsize=None)
def binomial(n, k):
	if n < k:
		return 0
	elif n < 2 * k:
		return binomial(n, n - k)
	else:
		numer = functools.reduce(operator.mul, range(n, n - k, -1), 1)
		denom = functools.reduce(operator.mul, range(k, 0, -1), 1)
		return numer // denom

def solve(xs):
	n = len(xs)
	for i in range(n):
		if i == 0:
			counts = 1
		counts *= binomial(sum(xs[:i + 1]) - 1, xs[i] - 1)
		counts %= LARGE_NUMBER
	return counts

@functools.lru_cache(maxsize=None)
def helper(xs, separators):
	print_stderr(xs, separators)
	if xs:
		k = xs[-1]
		ys = xs[:-1]
		result = []
		for i in range(k + 1):
			coeff = binomial(i + (separators - 1), i)
			out = coeff * helper(ys, separators + i - 1)
			result.append(out)
		return sum(result) % LARGE_NUMBER
	else:
		return 1

def print_stderr(*args, **kwargs):
	print(*args, file=sys.stderr, **kwargs)

def main():
	n = int(input())
	xs = [int(input()) for _ in range(n)]
	result = solve(xs)
	print(result)
main()


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))


k = int(input())
colors = []
for i in range(k):
	colors.append(int(input()))
ans = 1
accum = colors[0]
for i in range(1, k):
	for j in range(1, colors[i]):
		ans *= accum + j
	for j in range(1, colors[i]):
		ans //= j
	accum += colors[i]
print(ans % 1000000007)


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()