As the highlanders say, there are three kinds of truth: holy truth, "your" truth, and... the truth. Recent research by Byteotian logicians confirms this. They are studying logical expressions (propositional formulas) in a simplified form called clause form. The clause form is defined as follows:

• Formulas are built using logical variables $x_1, x_2, \ldots, x_n$. These variables can take the values true or false.
• A literal is a logical variable or its negation, $x_i$ or $\neg x_i$ (for $1 \le i \le n$).
• A clause is a conjunction of literals, e.g., $x_4 \wedge \neg x_2 \wedge x_3$.
• A formula is a disjunction of clauses, e.g., $(x_1 \wedge \neg x_2) \vee (\neg x_1 \wedge x_3) \vee (\neg x_3)$.

The value of a formula depends on the specific values of the variables. The values of the variables are determined by a function called a valuation, of the form $f : \{1, 2, \ldots, n\} \mapsto \{\text{true}, \text{false}\}$, where $f(i)$ is the value assigned to variable $x_i$. There are $2^n$ possible valuations in total. For a specific valuation, the value of a given formula is either true or false.

We say that a formula is true if its value is true for every valuation. We say that a formula is false if its value is false for every valuation. Often, a formula is neither true nor false, but its value actually depends on the given valuation. We can define the truthfulness of a formula as a fraction (in the range from 0 to 1):

$$\frac{\text{number of valuations for which the formula's value is true}}{2^n}$$

The number 1 corresponds to true formulas, and 0 to false formulas.

Examples

The formula:

$$(x_1 \wedge \neg x_1) \vee (\neg x_2 \wedge \neg x_3) \vee (x_3 \wedge x_2)$$

is true for four out of the eight possible valuations. Thus, it is true in half of the cases.

Task

You have 11 datasets available in [this archive]. Each set is saved in a separate file: fork.in, where $k$ is the set number ($0 \le k \le 10$). The file for0.in contains data consistent with the example above. Write a program that receives exactly one integer $k$ ($0 \le k \le 10$) as input and prints exactly one line of output containing the approximate truthfulness of the formula provided in the $k$-th dataset. The truthfulness should be printed as a decimal fraction, calculated with a relative accuracy of $3\%$. That is, if the truthfulness of the formula is $p$, and its calculated approximation is $p'$, then it must hold that $|p' - p| \le 0.03p$.

Input

The first line of input contains two positive integers $n$ and $m$, $1 \le n \le 100$, $1 \le m \le 100$, separated by a single space. The logical variables that may appear in the formula are $x_1, x_2, \ldots, x_n$. The formula consists of $m$ clauses, described in the following $m$ lines, one per line. Each of these lines contains integers separated by single spaces. The first of these numbers, $l$, $1 \le l \le n$, is the number of literals forming the clause. Following this in the line are $l$ integers representing the successive literals of the clause. These are non-zero numbers in the range from $-n$ to $n$. The number $i$ (for $1 \le i \le n$) represents $x_i$, and the number $-i$ represents $\neg x_i$.

Examples

Input 1

0

Output 1

0.5

Note

Accepted answers for the sample test also include: 0.485, 0.498, 0.51, 0.515.