Count Scorecards(30 points)

In a tournament, N players play against each other exactly once. Each game results in either of the player winning. There are no ties. You have given a scorecard containing the scores of each player at the end of the tournament. The score of a player is the total number of games the player won in the tournament. However, the scores of some players might have been erased from the scorecard. How many possible scorecards are consistent with the input scorecard?

Input:
The first line contains the number of cases T. T cases follow. Each case contains the number N on the first line followed by N numbers on the second line. The ith number denotes s_i, the score of the ith player. If the score of the ith player has been erased, it is represented by -1.

Output:
Output T lines, containing the answer for each case. Output each result modulo 1000000007.

Constraints:
1 <= T <= 20
1 <= N <= 40
-1 <= s_i < N

Sample Input:
5
3
-1 -1 2
3
-1 -1 -1
4
0 1 2 3
2
1 1
4
-1 -1 -1 2

Sample Output:
2
7
1
0
12


Explanation:
For the first case, there are 2 scorecards possible: {0,1,2} or {1,0,2}.
For the second case, the valid scorecards are {1,1,1}, {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}.
For the third case, the only valid scorecard is {0,1,2,3}.
For the fourth case, there is no valid scorecard. It is not possible for both players to have score 1.

Posted Date: 6/30/2012 6:58:09 PM | Location : United States

Ask an Expert

Related Discussions:- Dynamic programming., Assignment Help, Ask Question on Dynamic programming., Get Answer, Expert's Help, Dynamic programming. Discussions

Write discussion on Dynamic programming.
Your posts are moderated

Write your message here..

Related Questions

Search on a hashed file, Write a program to simulate searching over a hashe... Write a program to simulate searching over a hashed file, with different assumptions for the sizeof file pages.Write a program to perform equality search operations on the hashed f

Progrrame, how to write a code for for a company , for calculate the salary... how to write a code for for a company , for calculate the salary pay

Interest, I=PR/12 numbers of years : Interest Rate up to 1 years : 5... I=PR/12 numbers of years : Interest Rate up to 1 years : 5.50 Up to 5 years : 6.50 More than 5 year : 6.75 please design an algorithm based on the above information

Explain division method, Explain Division Method Division Method: - In... Explain Division Method Division Method: - In this method, key K to be mapped into single of the m states in the hash table is divided by m and the remainder of this division

FIRST function in the compiler construction, I need a recursive algorithm t... I need a recursive algorithm to implement the FIRST function to any grammar

Data type, Q. Define the terms data type and abstract data type. Comment up... Q. Define the terms data type and abstract data type. Comment upon the significance of both these.   Ans: We determine the total amount of memory to reserve by determining

Project, human resource management project work in c++ human resource management project work in c++

What are the advantages of using assertions, Using Assertions When writ... Using Assertions When writing code, programmer must state pre- and subtle post conditions for public operations, state class invariants and insert unreachable code assertions a

Indexed sequential file organisation, When there is requirement to access r... When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized

Financial index data analysis, need c++ algorithmic software program to der... need c++ algorithmic software program to derive one numerical outcome from 10 levels of variables with 135 combinations cross computed