该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

给你一个由 $n$ 个整数构成的可重复集合 $T=\{a_1\sim a_n\}$，假设 $S$ 为该集合的一个子集 $\{b_1\sim b_k\}$，则 $f(S)=(b_1+b_2+\cdots+b_k)^2$。
假设 $g(i)$ 表示所有元素个数为 $i$ 的子集的 $f$ 值之和，即 $g(i)=\sum_{S\subseteq T\ 且\ |S|=i}f(S)$。 分别求出 $g(1)\sim g(n)$的值（输出答案对 $10^9+7$ 取模的结果）。

【输入格式】

从文件sum.in中读入数据。

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数 $a_1\sim a_n$。

【输出格式】

输出到文件sum.out中。

• 一行 $n$ 个数，表示 $g(1)\sim g(n)$。

【输入样例 1】

5
1 2 3 4 5

【输出样例 1】

55 390 840 730 225

【输入输出样例 2】

见 sum2.in 与 sum2.ans

【数据范围与约定】

• 对于测试点 $1\sim 4$：$1\le n\le 20,0\le a_i \le 10^9$。
• 对于测试点 $5\sim 6$：$1\le n \le 3000,a_i=1$。
• 对于测试点 $7\sim 8$：$1\le n \le 3000,0\le a_i \le 1$。
• 对于测试点 $9\sim 20$：$1\le n \le 3000,0\le a_i \le 10^9$。