Inspector Gadget
Time Limit: 10 Seconds Memory Limit: 65536 KB
There are two keyboards for inputting password in a very old cave (supposedly full of treasure), a thief found this place and managed to get the password to enter. The thief used his left index finger to press the button on the left keyboard, and used his right index finger to press the button on the right keyboard. A layer of dust covered the buttons. Each time the thief pressed the button, the dust on his finger and on the button mixed to result in same amount of dust left on finger and button. At first, there is no dust on thief's fingers, and the amount of dust on each button is 1. Now, inspector gadget is on the crime scene in the cave and wants to know more about possible passwords by looking at the evidence. For each keyboard, we already know how many times its keys has been pressed. The question is how many possible passwords are there if the dust on the buttons is properly measured. Assume the left keyboard has 3 buttons: A B C which pressed 2 times, the right keyboard has 2 buttons: X Y which pressed once. If the amount of dust on the buttons are: The possible passwords are:
Input
There are multiple test cases. The first line of the input is an integer T < 1024, indicating the number of test cases. For each test case, there are 4 integers in the first line: N, M, P, Q. (1 ≤ N, M ≤ 5, 0 ≤ P, Q ≤ 10) N is the number of buttons on left keyboard, M is the number of buttons on right keyboard; P is the times of button pressed on left keyboard, Q is the times of button pressed on right keyboard. The following line of input contains N fractions indicate the amount of dust on the buttons of left keyboard, then a line contains M fractions indicate the amount of dust on the buttons of right keyboard. Input may contain empty lines.
Output
For each test case, output the number of possible passwords moduled by 10000007.
Sample Input
Sample Input 2 3 2 2 1 1 1/2 3/4 1/2 1 3 3 0 0 1 2 1 1 1 2
Sample Output
3 0Submit