Swedish coins (2) P20294

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 \dots p_n$. Assume $1 \le n \le 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$.