← 返回题目列表

Codeforces · 954/H

H. 路径计数

中文机器翻译题面 查看原题

你得到了一棵有根的树。我们将 d(x) 表示为节点 x 的深度:根的深度为 1,任何其他节点 x 的深度为 d(y) + 1,其中 y 是 x 的父节点。

该树具有以下属性:d(x) = i 的每个节点 x 都有 ai 个子节点。节点的最大可能深度为 n,且 an = 0。

我们将 fk 定义为树中无序顶点对的数量,使得它们之间的简单路径上的边数等于 k。

对于每个 1 ≤ k ≤ 2n - 2,计算 fk 模 109 + 7。

输入

输入的第一行包含一个整数 n (2 ≤ n ≤ 5 000) — 节点的最大深度。

输入的第二行包含 n - 1 个整数 a1, a2, ..., an - 1 (2 ≤ ai ≤ 109),其中 ai 是每个节点 x 的子节点数,使得 d(x) = i。由于 an = 0,因此输入中未给出。

输出

打印 2n - 2 个数字。这些数字的第 k 个必须等于 fk 模 109 + 7。

示例

输入 #1

4
2 2 2

输出 #1

14 19 20 20 16 16

输入 #2

3
2 3

输出 #2

8 13 6 9

注意

这是第一个样本中的树: