The statement of this problem is similar to the previous one. But here, you must solve a different problem:

Given a collection of coins C, how many subsets S of C are such that w(S) = 1/2?

Input

Input consists of several cases,
each one with n followed by p_{1} … p_{n}.
Assume 1 ≤ n ≤ 10^{5} and 0 < p_{i} < 1.

Output

For every case,
print the number of subsets S such that w(S) = 1/2.
Since this number can be huge,
compute it modulo 10^{8} + 7.

Public test cases

**Input**

1 0.3 5 0.5 0.5 0.5 0.5 0.5

**Output**

0 31

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++