#P9036. [2017年备战省选]a

[2017年备战省选]a

题目描述

有 nn 个编号为 1,2,…,n1,2,\ldots,n 的顶点,第 ii 个顶点的度数上限为 aia_i。对每个 x=1,2,…,nx=1,2,\ldots,n,求从这些顶点中选出 xx 个不同顶点构成一棵树的方案数。树中每个顶点的度数都不能超过该顶点的上限。

若两种方案选出的顶点集合不同,或存在一条边只出现在其中一棵树中,则这两种方案不同。

输入格式

第一行一个整数 TT,表示数据组数。

每组数据第一行一个整数 nn,第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

每组数据输出一行 nn 个整数,依次表示 x=1,2,…,nx=1,2,\ldots,n 时的方案数。每个答案对 109+710^9+7 取模。

样例

1
3
2 2 1
3 3 2

数据范围

对于第 kk 个测试点,n≤5kn\le 5k。所有测试点均满足 T≤10T\le 10、0≤ai≤n0\le a_i\le n。

原始题面见 1.pdf。