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_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⁹ + 7 for every 1 ≤ k ≤ 2n - 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₁, a₂, ..., a_n - 1 (2 ≤ a_i ≤ 10⁹), 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 2n - 2 numbers. The k-th of these numbers must be equal to f_k modulo 10⁹ + 7.

Note

This the tree from the first sample:

$\text{[math]}$

Path Counting

Examples