Swedish coins (2) P20294


Statement
 

pdf   zip

thehtml

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 p1pn. Assume 1 ≤ n ≤ 105 and 0 < pi < 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 108 + 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++