F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Tower Defense

Time 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 (109 + 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 (109 + 7) in a single line.

Sample Input
3
2 2 0 1
2 2 2 0
3 3 2 1


Sample Output
4
10
144


Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-08-14 19:09:03, Gzip enabled Administration