题目描述

给你一个由 $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 and \space |S|=i}f(S)$。 分别求出 $g(1)\sim g(n)$的值（输出答案对 $10^9+7$ 取模的结果）。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

5
1 2 3 4 5

输出 #1

55 390 840 730 225

说明/提示

对于所有测试点，满足：$1\le n \le 3000,0\le a_i \le 10^9$。