Random Numbers

5

1 votes
Easy-Medium
Problem

Felicity Smoak has two types of random number generators RNG1 and RNG2 and two arrays A and B each of size N.
RNG1 generates even numbers and RNG2 generates odd numbers.
Let x be the product of numbers present in array A and y be the product of numbers present in array B.
She generates x numbers using RNG1 and y numbers using RNG2.
She stores all these numbers in a very large array C.Now she chooses a subset of C. Given that sum of elements in the subset is even find the probability that all the numbers in the subset are those generated from RNG1.
If the probability is of the form p/q (where gcd(p,q)=1) print (p/q) mod (109+7)

If you help felicity in finding this number you may get a chance to be part of team arrow.

Input:

First line contains N.
Second line contains N space separated integers(elements of array A)
Third line contains N space separated integers(elements of array B)

Output:

Print the required answer

Constraints:

2<=N<=55000

1<=A[i]<=1010

1<=B[i]<=1010

Note:- Input files are large so use fast input and output methods.

Problem Setter : Teja Vojjala

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?