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 
#include<bits/stdc++.h>
using namespace std;
const long long md=1e9+7;
long long n,a[10101],ans[10101],f[10101],g[10101],pr[10101],vl[10101];
int main()
{
	cin>>n;
	pr[1]=1;
	for(int i=2;i<=n;i++)
	{
		cin>>a[i];
		pr[i]=pr[i-1]*a[i]%md;
	}
	f[0]=1;
	g[0]=1;
	for(int i=n-1;i>=1;i--)
	{
		memset(vl,0,sizeof(vl));
		for(int j=n;j>=1;j--)
		{
			f[j]=f[j-1]*a[i+1]%md;
		}
		for(int k=1;k<=n-i;k++)
		{
			vl[k]+=f[k];
			vl[k]%=md;
		}
		for(int k=2;k<=(n-i)*2;k++)
		{
			vl[k]+=a[i+1]*(a[i+1]-1)/2%md*g[k-2]%md;
			vl[k]%=md;
		}
		for(int j=1;j<=(n-i)*2;j++)
		{
			ans[j]+=pr[i]*vl[j]%md;
			ans[j]%=md;
		}
		for(int j=(n-i)*2;j>=2;j--)
		{
			g[j]=a[i+1]*a[i+1]%md*g[j-2]%md;
		}
		for(int j=2;j<=(n-i)*2;j++)
		{
			g[j]+=2*f[j];
			g[j]%=md;
		}
		g[1]=2*a[i+1]%md;
	}
	for(int i=1;i<=n*2-2;i++)
	{
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}