There are 2×N comedians and M audience member in a comedy show. The first N comedians are male and the last N are female.

There are 2×N comedians and M audience member in a comedy show. 

The first N comedians are male and the last N are female. In a comedy show, all the comics gets one slot to perform their act. The slots are alloted randomly and any allocation is equaly probable.

Each of the comdedians has a humour level given by the array A. The charge of each comedian is given by the array B.

Each of the audience member has a tolerance level given by array C and seriousness level given by array D. The gender of the member is given by the array E where E[i] = 1 denotes that member is male and E[i] = 2 denotes that member is female.

A comic of same gender as an audience member will make that member laugh if there have been atleast C[i] comics before them of the same gender such that their humour level is more than D[i] of that member.

A comic of opposite gender as an audience member will make that member laugh if there have been atleast C[i] comics before them of the same gender of the comic such that their humour level is more than the 2×D[i] of that member.

If a member laughs, then they have to pay that comedian B[i] coins.

What is the expected sum of amount that all the comedians will earn in a single show. Express the expected sum as an irreducible fraction u / v, then you have to find the value of u × v-1 mod 109+7.

Problem Constraints

1 <= N <= 105

1 <= M <= 105

1 <= A[i] <= 109

1 <= B[i] <= 109

1 <= C[i] <= N

1 <= D[i] <= 109

1 <= E[i] <= 2

Input Format

First argument A is an integer array denoting the humour level of each comedian

Second argument B is an integer array denoting the charge of each comedian

Third argument C is an integer array denoting the tolerance level of each audience member

Fourth argument D is an integer array denoting the seriousness level of each audience member

Fifth argument E is an integer array denoting the gender of each audience member

Output Format

Return an integer denoting the expected sum of amount that all the comedians will earn in a single show

 

Example Input

Input 1:

A = [20, 2, 8, 17]

B = [16, 8, 8, 6]

C = [1, 1]

D = [6, 9]

E = [1, 2]

Input 2:

A = [20, 2, 8, 17]

B = [16, 8, 8, 6]

C = [1, 1]

D = [9, 6]

E = [1, 2]

Example Output

Output 1:

16

Output 2:

15

Example Explanation

For Input 1:

The first audience member will laugh during the act of 2-nd comic if 1-st comic performed before him.

He will laugh during the performance of 3-rd comic if the 4-th comic have performed before.

Both these have a 50% probabilty, so the expect sum that the first member pays is (8 + 8) / 2 = 8

The second audience member will laugh during the act of 2-nd comic, if the 1-st comic performed before him.

She will laugh during the act of 3-rd comic if the 4-th comic performed before her.

Both these have a 50% probability, so the expected sum that the second member pays is (8 + 8) / 2 = 8

So the net expected sum the comedians make in the show is 8 + 8 = 16.

For Input 2:

The first audience member will laugh during the act of 2-nd comic if 1-st comic performed before him.

This have a 50% probabilty, so the expect sum that the first member pays is 8 / 2 = 4

The second audience member will laugh during the act of 2-nd comic, if the 1-st comic performed before him.

She will laugh during the act of 3-rd comic if the 4-th comic performed before her.

She will laugh during the act of 4-th comic if the 3-rd comic performed before her.

All these have a 50% probability, so the expected sum that the second member pays is (8 + 8 + 6) / 2 = 11

So the net expected sum the comedians make in the show is 4 + 11 = 15.

To find the expected sum of amount that all the comedians will earn in a single show, we can iterate through each comedian and calculate the expected sum of amount they will earn in the show.

For each comedian, we can iterate through each audience member and calculate the probability that the audience member will laugh during the comedian's act. We can then multiply this probability by the charge of the comedian to find the expected sum of amount that the comedian will earn from that audience member. We can add up the expected sum of amount that the comedian will earn from each audience member to find the expected sum of amount that the comedian will earn in the show.

Finally, we can add up the expected sum of amount that each comedian will earn in the show to find the expected sum of amount that all the comedians will earn in the show.

Here is some example code in Python that demonstrates this approach:

Python

MOD = 1000000007 def expectedSum(A, B, C, D, E): # Initialize the expected sum of amount that all the comedians will earn in the show to 0 expected_sum = 0 # Iterate through each comedian for i in range(len(A)): # Initialize the expected sum of amount that the comedian will earn in the show to 0 comedian_expected_sum = 0 # Iterate through each audience member for j in range(len(C)): # Calculate the probability that the audience member will laugh during the comedian's act if E[j] == 1: # If the comedian and the audience member are of the same gender if i < len(A) / 2: # If the comedian is male if i >= C[j]: # If there have been at least C[j] comics before the comedian of the same gender if A[i] > D[j]: # If the humour level of the comedian is more than D[j] probability = 1 else: probability = 0 else: probability = 0 else: # If the comedian is female probability = 0 else: # If the comedian and the audience member are of different genders if i < len(A) / 2: # If the comedian is male if i >= C[j]: # If there have been at least C[j] comics before the comedian of the same gender if A[i] > 2 * D[j]: # If the humour level of the comedian is more than 2 * D[j] probability = 1 else: probability = 0 else: probability = 0 else: # If the comedian is female if i >= C[j] + len(A) / 2: # If there have been at least C[j] comics before the comedian of the same gender if A[i] > 2 * D[j]: # If the humour level of the comedian is more than 2 * D[j] probability = 1 else: probability = 0 else: probability = 0 # Add the expected sum of amount that the comedian will earn from the audience member to the expected sum of amount that the comedian will earn in the show comedian_expected_sum += (probability * B[i]) % MOD