You are given a rooted tree. Let's denote *d*(*x*) as depth of node *x*: depth of the root is 1, depth of any other node *x* is *d*(*y*) + 1, where *y* is a parent of *x*.

The tree has the following property: every node *x* with *d*(*x*) = *i* has exactly *a*<sub class="lower-index">*i*</sub> children. Maximum possible depth of a node is *n*, and *a*<sub class="lower-index">*n*</sub> = 0.

We define *f*<sub class="lower-index">*k*</sub> as the number of unordered pairs of vertices in the tree such that the number of edges on the simple path between them is equal to *k*.

Calculate *f*<sub class="lower-index">*k*</sub> modulo 10<sup class="upper-index">9</sup> + 7 for every 1 ≤ *k* ≤ 2*n* - 2.
The first line of input contains an integer *n* (2  ≤  *n*  ≤  5 000) — the maximum depth of a node.

The second line of input contains *n* - 1 integers *a*<sub class="lower-index">1</sub>,  *a*<sub class="lower-index">2</sub>,  ...,  *a*<sub class="lower-index">*n* - 1</sub> (2 ≤  *a*<sub class="lower-index">*i*</sub>  ≤ 10<sup class="upper-index">9</sup>), where *a*<sub class="lower-index">*i*</sub> is the number of children of every node *x* such that *d*(*x*) = *i*. Since *a*<sub class="lower-index">*n*</sub> = 0, it is not given in the input.
This the tree from the first sample:
4
2 2 2
14 19 20 20 16 16 
3
2 3
8 13 6 9 
2
2
2 1 
6
2 2 4 2 4
182 415 420 980 1216 2432 1536 3328 2048 4096 
M=10**9+7
def modpow(x, p):
    if p==0:
        return 1
    if p<0:
        return modpow(x, (2-M)*p)
    y=modpow(x, p//2)
    if p%2:
        return (y*y*x)%M
    return (y*y)%M
def modhyp(x):
    return modpow(x, -1)
n=int(input())
a=[0]+[int(e) for e in input().split()]+[0]*(n+1)
b=[0, a[1]]
for i in range(2, len(a)):
    b.append((b[-1]*a[i])%M)
def p(i, j):
    if j<i:
        return 1
    if b[i]==0 or b[j]==0:
        return 0
    if i==1:
        return b[j]
    return (b[j]*modhyp(b[i-1]))%M
ANS=[]
for k in range(1, 2*n-1):
    ans=0
    for x in range(k//2+1):
        for i in range(1, n+1):
            res=p(1, i-1)
            if x==0:
                res*=p(i, i+k-1)
            elif x==k-x:
                res*=p(i, i+x-1)*(a[i]-1)*p(i+1, i+x-1)*modhyp(2)
            else:
                res*=p(i, i+x-1)*(a[i]-1)*p(i+1, i+x-1)*p(i+x, i+k-x-1)
            res%=M
            ans+=res
            ans%=M
    ANS.append(ans)
print(*ANS)