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₁ … p_n. Assume 1 ≤ n ≤ 10⁵ 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⁸ + 7.