Problem 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.

2 
4 
2 2 2 2 
4 
3 3 3 3 

12 
16