SpaceStation

Time Limit: 2000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2667
64-bit integer IO format: %I64d      Java class name: Main

Description

N space stations are built in the space, and flights should be set among these space stations. Flights are bidirectional, and connect different space stations. A valid arrangement of flights must satisfy the rules below:
1. Every space station can be reached from all others via flights directly or indirectly.
2. Because the spaceships are too expensive, the number of flights should be minimal.
3. Due to the limited resource of service and communication, the number of flights directly connected to each space station is limited.
Here comes the problem: how many different valid arrangements can be set?
Two arrangements A and B are different means that, there exists at least one flight in A but not in B, or there exists at least one flight in B but not in A.

Input

The input contains multiple test cases.
The first line contains an integer T, 0 < T <= 20, representing the number of test cases.
For each test case:
The first line contains an integer N, 0 < N <= 300, representing the number of space stations. The second line contains N integers K1、K2 ? KN, 0 <= Ki <= N - 1,Ki, separated by blanks, representing the maximal flights directly connected to the i-th space station.

Output

For each test case:
Output one line containing an integer ? the number of arrangements in total modulo 9973.

Sample Input

2 
4 
2 2 2 2 
4 
3 3 3 3

Sample Output

12 
16

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .