Truth Fraction of a Formula

The highlanders say there are three kinds of truth: the holy truth, also the truth, and the plain truth. Logicians in Byteland decided to check the saying by measuring how true a formula written in clausal form really is.

• Formulas are built from the logical variables $x_1, x_2, \dots, x_n$. Each variable is either true or false.
• A literal is a logical variable or its negation, that is $x_i$ or $\lnot x_i$ ($1 \le i \le n$).
• A clause is a conjunction of literals, for instance $x_4 \land \lnot x_2 \land x_3$.
• A formula is a disjunction of clauses, for instance $(x_1 \land \lnot x_2) \lor (\lnot x_1 \land x_3) \lor (\lnot x_3)$.

The value of a formula depends on the values given to its variables. A function that assigns a value to every variable is called a valuation and is written as $f : \{1, 2, \dots, n\} \to \{\text{true}, \text{false}\}$, where $f(i)$ is the value given to $x_i$. There are $2^n$ valuations in total, and once a valuation is fixed the formula is either true or false.

A formula that is true under every valuation is a tautology, and a formula that is false under every valuation is a contradiction. Most formulas are neither, so their value really depends on the valuation. How true a formula is can therefore be written as a fraction between 0 and 1:

$\frac{\text{number of valuations under which the formula is true}}{2^n}$

The value 1 belongs to tautologies and the value 0 to contradictions.

For example, $(x_1 \land \lnot x_1) \lor (\lnot x_2 \land \lnot x_3) \lor (x_3 \land x_2)$ is true under four of the eight valuations, so its truth fraction is $1/2$.

Given a formula, compute its truth fraction exactly.

The first line contains the integers $n$ and $m$ separated by a single space ($1 \le n \le 20$, $1 \le m \le 100$). The variables that may appear in the formula are $x_1, x_2, \dots, x_n$, and the formula consists of $m$ clauses.

Each of the next $m$ lines describes one clause and holds integers separated by single spaces. The first integer $l$ on the line is the number of literals in that clause, $1 \le l \le n$. It is followed by $l$ integers that describe the literals in order. All of them are nonzero and lie between $-n$ and $n$. The integer $i$ stands for $x_i$ and the integer $-i$ stands for $\lnot x_i$ ($1 \le i \le n$).

The same variable may appear several times in one clause, and a variable may appear together with its own negation. A clause that holds both a variable and its negation is false under every valuation.

Print one line with the exact truth fraction of the formula. The fraction has denominator $2^n$, so it can be written exactly as a terminating decimal with at most $n$ digits after the decimal point. Do not print trailing zeros after the decimal point.

Print 0 if the formula is false under every valuation and 1 if it is true under every valuation. In all remaining cases the answer is greater than 0 and smaller than 1, so print a decimal that starts with 0..