Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3586
Press the Button

Time Limit: 2 Seconds      Memory Limit: 131072 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. If we already know how many times are pressed on each keyboard, 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 is:

  • A:1
  • B:1/2
  • C:3/4
  • X:1/2
  • Y:1

The possible passwords are:

  • BCX
  • BXC
  • XBC

Input

The input consists of several test cases. For each 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.

A test case started with four zeros indicates the end of the input. Input may contain empty lines.

Output

For each test case, output the number of possible passwords moduled by 10000007.

Sample Input

3 2 2 1
1 1/2 3/4
1/2 1
3 3 0 0
1 2 1
1 1 2
0 0 0 0

Sample Output

3
0

Author: ZHENG, Jianqiang
Contest: ZOJ 10th Anniversary Contest
Submit    Status