A. 86
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

The Republic of San Magnolia is at war against the autonomous Legion forces and is currently on the back foot. The Republic's military operates $$$n$$$ combat units on the battlefield, and if too many of them are destroyed, the Republic will be forced to abandon the front.

Each day, the Legion launches an attack on every unit exactly once. However, not all attacks are guaranteed to destroy a unit, as each unit is equipped with defensive systems. For the $$$i$$$-th unit, there is a $$$\dfrac{x_i}{y_i}$$$ probability that a single attack will destroy it. Otherwise, the attack is repelled, and the unit remains operational for the day, taking no damage.

All attacks across different units and on different days are independent. Once a unit is destroyed, it remains destroyed and cannot become operational again.

You are a citizen trying to understand how long the Republic can continue the war. However, due to misinformation and limited access to the battlefield, different sources report different states of the front lines. Each report claims that a subset of units is operational, which means all others are already destroyed.

The Republic can continue fighting as long as at least $$$k$$$ units remain operational. The front will collapse as soon as fewer than $$$k$$$ units remain.

For each report, determine the expected number of days the Republic can continue fighting, on the condition that the report is accurate.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10)$$$ — the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ $$$(1 \le n \le 17)$$$ and $$$r$$$ $$$(1 \le r \le 10^5)$$$ — the number of combat units and the number of reports.

The second line of each test case contains $$$n$$$ space-separated integers $$$x_1, x_2, \dots, x_n$$$ $$$(1 \le x_i \le 10^6)$$$ — the numerators of the probabilities of the units being destroyed in a single attack.

The third line of each test case contains $$$n$$$ space-separated integers $$$y_1, y_2, \dots, y_n$$$ $$$(x_i \le y_i \le 10^6)$$$ — the denominators of the probabilities of the units being destroyed in a single attack.

The next $$$2r$$$ lines of each test case describe the $$$r$$$ reports. Each report is described as follows:

The first line of each report contains two space-separated integers $$$m$$$ and $$$k$$$ $$$(1 \le k \le m \le n)$$$ — the number of operational units, and the minimum number of operational units required to continue the war.

The second line of each report contains $$$m$$$ distinct space-separated integers $$$b_1, b_2, \dots, b_m$$$ $$$(1 \le b_i \le n)$$$ — the indices of the units that are operational.

It is guaranteed that the sum of $$$(n \times r)$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output $$$r$$$ space-separated integers in a line — the expected number of days the Republic can continue fighting for each report, modulo $$$(10^9 + 7)$$$.

Formally, if the expected number of days can be represented as an irreducible fraction $$$\dfrac{p}{q}$$$, output the integer $$$p \times q^{-1} \bmod (10^9 + 7)$$$, where $$$q^{-1}$$$ is an integer such that $$$q \times q^{-1} \bmod (10^9 + 7) = 1$$$.

Example
Input
3
3 2
1 1 2
7 5 9
1 1
1
2 1
2 3
5 1
1 1 1 1 1
1 1 1 1 1
5 2
1 2 3 4 5
10 3
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2
1 1
10
10 1
1 2 3 4 5 6 7 8 9 10
10 10
1 2 3 4 5 6 7 8 9 10
Output
7 617647070
1
2 254032441 94819161
Note

For the first test case, only one unit is operational according to the first report. Every day, the unit has a $$$\dfrac{1}{7}$$$ probability of being destroyed. The expected survival duration of that unit is $$$7$$$ days. For the second report, the expected duration of the battle is $$$\dfrac{233}{34}$$$ days.