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 
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n = int(input())
a = list(map(int, input().split()))
mod = pow(10, 9) + 7
ans = [0] * (2 * n - 2)
b = list(a)
for i in range(1, n - 1):
    b[i] *= b[i - 1]
    b[i] %= mod
s = 0
for i in range(n - 2, -1, -1):
    s += b[i]
    s %= mod
    ans[i] = s
dp = [0] * (2 * n - 2)
for i in range(n - 1):
    bi = b[i]
    for j in range(i, n - 1):
        bj = 2 * b[j] % mod if i ^ j else b[j]
        dp[i + j + 1] += bi * bj % mod
        dp[i + j + 1] %= mod
l = 0
s = pow(2, mod - 2, mod)
for i in range(n - 1):
    ai = a[i]
    inv = pow(ai, mod - 2, mod)
    for _ in range(2):
        s *= inv
        s %= mod
    c = ai * (ai - 1) % mod * s % mod
    s *= ai
    s %= mod
    for j in range(l, 2 * n - 2):
        ans[j - l] += c * dp[j] % mod
        ans[j - l] %= mod
    l += 2
    bi = b[i]
    for j in range(i, n - 1):
        bj = 2 * b[j] % mod if i ^ j else b[j]
        dp[i + j + 1] -= bi * bj % mod
        dp[i + j + 1] %= mod
sys.stdout.write(" ".join(map(str, ans)))