random-numbers

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 (10^9+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] ≤ 10^{10}

1 ≤ B[i] ≤ 10^{10}

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

Problem Setter : Teja Vojjala

SAMPLE INPUT
2
1 2
2 3

SAMPLE OUTPUT
710937505

Source: hackerearth | Difficulty: EASY


Solutions: