你得到了一棵有根的树。我们将 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
注意
这是第一个样本中的树: