

Tower DefenseTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)Total Submission(s): 1283 Accepted Submission(s): 401 Problem Description DRD loves playing computer games, especially Tower Defense games. Tower Defense is a famous computer game with a number of variations. In general, you are to build some defense towers to guard your territory in this game. However, in most Tower Defense games, your defending towers will not attack each other. You will see the shells flying through your towers and finally hit the target on your screen. DRD thinks it to be absurd, and he designed a new tower defense game. In DRD’s game, you have two kinds of defending tower, heavy tower and light tower. You can put the tower on a grid with N rows and M columns and each cell in the grid can hold one tower at most. Both two kinds of towers can attack the cells in the same column or the same row as it is located in, and your towers may attack each other. Moreover, light towers should not be attacked by other towers while heavy towers can be attacked by at most one other tower. You can put some of your towers (at least one tower) in the grid to build a tower formation satisfying the restriction above. And now, DRD wants you to calculate that how many different tower formations could be designed. Note that all the towers of the same type are considered to be identical. While the answer could be quite large, you should output the number mod (10^{9} + 7). Input There are multiple test cases in the input. The first line of the input file is an integer T demonstrating the number of test cases. (0< T<= 200). For each test case, there is only one line containing 4 integers, N, M, P and Q ,meaning that the grid has N rows and M columns, and you have P heavy towers and Q light towers. You do not have to put all the towers in the grid. (1 <= N, M <= 200, 0 <= P, Q <= 200) Output For each test case, output the number of different formations mod (10^{9} + 7) in a single line. Sample Input
Sample Output
Source  
