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

Difficulty: competition

Starter code:

Solutions:
3

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)


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)


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 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(1e9 + 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()


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

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

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)

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)


s = int(input())
MOD = int(1e9 + 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)


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)


#copied...


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)


# coding=utf-8

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)


import math

def euclid_algorithm(a, b):
    t1, t2 = abs(a), abs(b)
    #saving equalities:
    #t1 == x1 * a + y1 * b,
    #t2 == x2 * a + y2 * 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
        #t1 - k * t2 == (x1 - k * x2) * a + (y1 - k * y2) * b
        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)


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)


def __starting_point():
    main()

__starting_point()

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)


#copied...



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

#  C:\Users\Usuario\HOME2\Programacion\ACM


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)


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)

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


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


#copied...




# Made By Mostafa_Khaled


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)

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:]):
#for i in range(0,numeroColores-1):
    anterior+= 1
    #reset
    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:
    #Aplicar modulo
    conclusion = conclusion% 1000000007
print(conclusion)