Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

H. Path Counting

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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*_{i} children. Maximum possible depth of a node is *n*, and *a*_{n} = 0.

We define *f*_{k} 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*_{k} modulo 10^{9} + 7 for every 1 ≤ *k* ≤ 2*n* - 2.

Input

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*_{1}, *a*_{2}, ..., *a*_{n - 1} (2 ≤ *a*_{i} ≤ 10^{9}), where *a*_{i} is the number of children of every node *x* such that *d*(*x*) = *i*. Since *a*_{n} = 0, it is not given in the input.

Output

Print 2*n* - 2 numbers. The *k*-th of these numbers must be equal to *f*_{k} modulo 10^{9} + 7.

Examples

Input

4

2 2 2

Output

14 19 20 20 16 16

Input

3

2 3

Output

8 13 6 9

Note

This the tree from the first sample:

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/21/2018 18:49:53 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|