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 $\ell$ and $r$, and a collection of coins $C$, how many subsets $S$ of $C$ are such that $\ell < w(S) < r$?

Input

Input consists of several cases. Every case begins with two real numbers $\ell$ and $r$, followed by $n$, followed by $p_1 \dots p_n$. Assume $0 < \ell < r < 1$, $1 \le n \le 40$ and $0 < p_i < 1$.

Output

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

Observation

Please take into account that the result can be larger than $10^{12}$.