#P9036. [2017年备战省选]a
[2017年备战省选]a
题目描述
有 个编号为 的顶点,第 个顶点的度数上限为 。对每个 ,求从这些顶点中选出 个不同顶点构成一棵树的方案数。树中每个顶点的度数都不能超过该顶点的上限。
若两种方案选出的顶点集合不同,或存在一条边只出现在其中一棵树中,则这两种方案不同。
输入格式
第一行一个整数 ,表示数据组数。
每组数据第一行一个整数 ,第二行 个整数 。
输出格式
每组数据输出一行 个整数,依次表示 时的方案数。每个答案对 取模。
样例
1
3
2 2 1
3 3 2
数据范围
对于第 个测试点,。所有测试点均满足 、。
原始题面见 1.pdf。