Orange的集合选数

题目描述

Orange有一个大小为 $n$ 的可重集合 $S = \{a_1,a_2,...,a_n\}$。

Orange规定，对于一个 $S$ 的子集 $U(U \subseteq S)$,函数 $f(U)$ 表示 $U$ 的元素之和的平方，即:

$$f(U) = (\sum_{x \in U} x)^2$$

同时，我们还规定 $G(x)$ 表示所有大小为 $x$ 的 $S$ 的子集的 $f$ 之和，即：

$$G(x) = \sum_{U \subseteq S \ \text{and} \ |U|=x} f(U)$$

你的任务是，求出每个 $G(x)$ 的值，即求出 $G(1),G(2),...,G(n)$。由于答案可能很大，请输出答案对 $10^9+7$ 取 $\bmod$ 的值即可。

输入格式

输入共2行： 第一行为一个整数 $n$，表示集合 $S$ 大小。 第二行包含 $n$ 个整数 $a_i$，表示 $S$ 中的所有元素。

数据范围

$n \le 3000$ $a_i \le 10^9$

输出格式

输出一行，包含 $n$ 个整数，依次为 $G(1),G(2),...,G(n)$ 的值，对 $10^9+7$ 取 $\bmod$。

样例 #1

样例输入 #1

5
1 2 3 4 5

样例输出 #1

55 390 840 730 225