CF954H.Path Counting

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 109 + 7 for every 1 ≤ k ≤ 2_n_ - 2.

给你一棵有根树。记 $ d(x) $ 为节点 $ x $ 的深度：根节点的深度为 $ 1 $，其余任意节点 $ x $ 的深度为 $ d(y) + 1 $，其中 $ y $ 是 $ x $ 的父节点。

该树具有如下性质：每个满足 $ d(x) = i $ 的节点 $ x $ 恰好有 $ a_i $ 个子节点。节点的最大可能深度为 $ n $，且 $ a_n = 0 $。

我们定义 $ f_k $ 为树中无序顶点对的数量，使得它们之间简单路径上的边数恰好等于 $ k $。

对每个 $ 1 \leq k \leq 2n - 2 $，计算 $ f_k $ 对 $ 10^9 + 7 $ 取模的结果。

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  ≤ 109), 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.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 5\,000$）—— 表示节点的最大深度。

输入的第二行包含 $n-1$ 个整数 $a_1,\,a_2,\,\dots,\,a_{n-1}$（$2 \leq a_i \leq 10^9$），其中 $a_i$ 表示所有满足 $d(x) = i$ 的节点 $x$ 的子节点数目。由于 $a_n = 0$，故不包含在输入中。

Print 2_n_ - 2 numbers. The k-th of these numbers must be equal to f__k modulo 109 + 7.

输出 $2n - 2$ 个数。其中第 $k$ 个数必须等于 $f_k \bmod (10^9 + 7)$。

This the tree from the first sample:

这是第一个样例中的树：