Dr. Chrono unsolved

dr-chrono-unsolved.txt

In a movie theatre, there are N * M seats, arranged as a grid of N rows and M columns. You've decided that if you sell a movie seat, you won't sell another seat present in any of the earlier rows in the same column, or the immediately adjacent columns. This is because the person sitting in the earlier row can obstruct the view of the person sitting behind him in an adjacent column.

In other words, if you put a person k in the middle of a 4x3 grid:

ooo

ooo

oko

ooo

the following seats 'b' will be blocked (assuming the screen is on the top of the grid):

bbb

bbb

oko

ooo

In how many ways can K seats be sold?


Input :
The first line contains T the number of test cases. Each of the next T lines contain 3 integers : N, M and K.

Output :
Output T lines, one for each test case, containing the desired answer for the corresponding test case. Output all answers modulo 1000000007.

Constraints :
1 <= T <= 100
1 <= N <= 100000
1 <= M <= 100000
1 <= K <= M

Sample Input :
3
3 2 1
5 3 2
5 3 3

Sample Output :
6
35
5

Explanation:

For the first case, there is just one seat to be sold, which can be any of the 6 seats.

For the second case, if two seats from adjacent columns are sold, they need to be from the same row. There are 5 * 2 ways to do this. Otherwise if two seats are from non-adjacent columns, the first will be from column 1 and the second from column 3. There are 5 * 5 ways to do this. So the answer is 10 + 25 = 35.

For the third case, all seats sold should be in the same row. There are 5 ways to do this.

One of the apps by drchrono helps hospitals in scheduling the timing of doctors. In a hospital there are N doctors and a set of working shifts. Each of the shifts are of same length and are divided into equal number of slots in which a doctor can see a patient. Every doctor has his preference for the maximum total number of slots he can work and also the specific slots in a shift in which he prefers to work. None of the doctors want to work in more than two slot in the same shift and no two doctors can be assigned to the same slot in the same shift
Satisfying all the constraints given, your task is to assign the given doctors to the slots they prefer in a way that maximizes the total number of slots to which a doctor is assigned.
 
Taking a concrete example, say there is a hospital with two doctors( Dr. A and Dr. B) and two working-shifts of 4 slots each. Dr A can work for at most two slots and he prefers working only in slot-1 and slot-3 of first shift while slot-3 and slot-4 of the second shift. Dr. B can work for at most 3 slots and he prefers working only in slot-2 and slot-3 of first shift and slot-1 and slot-4 of second shift.
 
One possible assignment is to assign Dr. A slot-1 from first shift and slot-4 from second shift, and to Dr. B slot-2 and slot-3 from first shift and slot-1 from second shift. So in total we have 5 slots which have a doctor assigned to them.
 
Input Format:
First line contains three space integers N, S and D. N is the number of doctors, S is the number of slots in a working-shift and D is the total number of working-shifts.
Next line contains N space seperated integers, ith integer is the maximum number of slots for which the ith doctor can work.
Then follows an empty line.
Then for each of the N doctors there is a block of D lines.
In the ith line of each block, 1st number denotes the number of slots which the doctor prefers for the ith shift and then there is a space separated list of slot numbers in that shift , the doctor likes to work in.
Each block of D lines is seperated by a blank line.
Note:Ignore trailing white spaces at the end of any line
 
Output Format:
Print a single number that is the maximum number of slots that have a doctor assigned to them.
 
Sample Input:
4 3 2
4 2 4 2

1 3 
2 1 2

2 1 2 
2 2 1

1 1 
1 2

1 3 
1 2

Sample Output:

5

Explanation of Sample Input:

Ist line contains 4, 3 and 2. So there are 4 doctors, 2 working-shifts and each shift in divided into 3 slots.

Next line denotes that each of the first and third doctor can work for at most 4 slots, while the second and fourth one can work for maximum of 2 slots in total.

Then there are 4 blocks of two lines each, ith block is for the ith doctor. Here for example, the first doctor prefers one slot in first shift namely slot-3 while in the second shift he prefers to work in slot-1 and slot-2.

Constraints:
1 <= N <= 50 
1 <= S <= 50
1 <= D <= 6