Swedish coins (1) P95248

You have a collection C of n old Swedish coins. Every coin i has a probability p_i of landing heads (and a probability 1 − p_i of landing tails). Consider the following experiment for every subset S of C: Flip each coin in S exactly once, and count the number of heads; you win if this number is odd. Let w(S) denote the winning probability of the subset S.

Given two real numbers ℓ and r, and a collection of coins C, how many subsets S of C are such that ℓ < w(S) < r?

Input

Input consists of several cases. Every case begins with two real numbers ℓ and r, followed by n, followed by p₁ … p_n. Assume 0 < ℓ < r < 1, 1 ≤ n ≤ 40 and 0 < p_i < 1.

Output

For every case, print the number of subsets S such that ℓ < w(S) < r. The input cases have no precision issues.

Observation

Please take into account that the result can be larger than 10¹².