{"raw_statement":[{"iden":"statement","content":"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_.\n\nThe 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.\n\nWe 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_.\n\nCalculate _f__k_ modulo 109 + 7 for every 1 ≤ _k_ ≤ 2_n_ - 2."},{"iden":"input","content":"The first line of input contains an integer _n_ (2  ≤  _n_  ≤  5 000) — the maximum depth of a node.\n\nThe 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."},{"iden":"output","content":"Print 2_n_ - 2 numbers. The _k_\\-th of these numbers must be equal to _f__k_ modulo 109 + 7."},{"iden":"examples","content":"Input\n\n4\n2 2 2\n\nOutput\n\n14 19 20 20 16 16 \n\nInput\n\n3\n2 3\n\nOutput\n\n8 13 6 9"},{"iden":"note","content":"This the tree from the first sample:\n\n<center>![image](https://espresso.codeforces.com/81cc5f2767d9eec33aa1efcb47ef6a4872480934.png)</center>"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"你被给定一棵有根树。记 #cf_span[d(x)] 为节点 #cf_span[x] 的深度：根节点的深度为 #cf_span[1]，其他任意节点 #cf_span[x] 的深度为 #cf_span[d(y) + 1]，其中 #cf_span[y] 是 #cf_span[x] 的父节点。\\n\\n这棵树具有以下性质：每个满足 #cf_span[d(x) = i] 的节点 #cf_span[x] 恰好有 #cf_span[ai] 个子节点。节点的最大可能深度为 #cf_span[n]，且 #cf_span[an = 0]。\\n\\n我们定义 #cf_span[fk] 为树中满足简单路径上边数恰好为 #cf_span[k] 的无序顶点对的数量。\\n\\n请对每个 #cf_span[1 ≤ k ≤ 2n - 2]，计算 #cf_span[fk] 对 #cf_span[109 + 7] 取模的结果。\\n\\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[2  ≤  n  ≤  5 000]) —— 节点的最大深度。\\n\\n输入的第二行包含 #cf_span[n - 1] 个整数 #cf_span[a1,  a2,  ...,  an - 1] (#cf_span[2 ≤  ai  ≤ 109])，其中 #cf_span[ai] 表示每个满足 #cf_span[d(x) = i] 的节点 #cf_span[x] 的子节点数。由于 #cf_span[an = 0]，该值不在输入中给出。\\n\\n请输出 #cf_span[2n - 2] 个数。第 #cf_span[k] 个数必须等于 #cf_span[fk] 对 #cf_span[109 + 7] 取模的结果。\"}},{\"iden\":\"input\",\"content\":\"输入的第一行包含一个整数 #cf_span[n] (#cf_span[2  ≤  n  ≤  5 000]) —— 节点的最大深度。输入的第二行包含 #cf_span[n - 1] 个整数 #cf_span[a1,  a2,  ...,  an - 1] (#cf_span[2 ≤  ai  ≤ 109])，其中 #cf_span[ai] 表示每个满足 #cf_span[d(x) = i] 的节点 #cf_span[x] 的子节点数。由于 #cf_span[an = 0]，该值不在输入中给出。\"},{\"iden\":\"output\",\"content\":\"请输出 #cf_span[2n - 2] 个数。第 #cf_span[k] 个数必须等于 #cf_span[fk] 对 #cf_span[109 + 7] 取模的结果。\"},{\"iden\":\"examples\",\"content\":\"输入\\n4\\n2 2 2\\n输出\\n14 19 20 20 16 16\\n\\n输入\\n3\\n2 3\\n输出\\n8 13 6 9 \"},{\"iden\":\"note\",\"content\":\"这是第一个样例中的树：  \"}]","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 5000 $.  \nLet $ a_i \\in \\mathbb{Z} $ for $ 1 \\leq i \\leq n-1 $, where $ a_i \\geq 2 $, and $ a_n = 0 $.  \nThe tree is rooted at node of depth 1.  \nFor each node $ x $ at depth $ i $ ($ 1 \\leq i < n $), it has exactly $ a_i $ children.  \nNodes at depth $ n $ are leaves (no children).  \n\nLet $ d(x) $ denote the depth of node $ x $, with $ d(\\text{root}) = 1 $.  \nLet $ V $ be the set of all nodes in the tree.  \nLet $ f_k $ be the number of unordered pairs $ \\{u, v\\} \\subseteq V $, $ u \\ne v $, such that the distance (number of edges) on the unique simple path between $ u $ and $ v $ is exactly $ k $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 5000 $  \n2. $ 2 \\leq a_i \\leq 10^9 $ for $ 1 \\leq i \\leq n-1 $  \n3. $ a_n = 0 $ (implicit)  \n4. Compute $ f_k \\mod (10^9 + 7) $ for all $ 1 \\leq k \\leq 2n - 2 $\n\n**Objective**  \nFor each $ k \\in \\{1, 2, \\dots, 2n-2\\} $, compute:  \n$$\nf_k = \\left| \\left\\{ \\{u, v\\} \\subseteq V \\,\\middle|\\, u \\ne v,\\, \\text{dist}(u,v) = k \\right\\} \\right| \\mod (10^9 + 7)\n$$","simple_statement":null,"has_page_source":false}