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++