논리식이 참인 비율

산골 사람들 말로는 진실에 세 가지가 있다고 한다. 성스러운 진실, 그것도 진실, 그리고 그냥 진실. 바이트란드의 논리학자는 이 말을 확인하려고, 절 형태로 쓴 논리식이 얼마나 참인지를 재기로 했다.

• 논리식은 논리 변수 $x_1, x_2, \dots, x_n$으로 만든다. 각 변수의 값은 참 아니면 거짓이다.
• 리터럴은 논리 변수 하나이거나 그 부정이다. 즉 $x_i$ 또는 $\lnot x_i$ ($1 \le i \le n$)이다.
• 절은 리터럴의 논리곱이다. 예를 들면 $x_4 \land \lnot x_2 \land x_3$이다.
• 논리식은 절의 논리합이다. 예를 들면 $(x_1 \land \lnot x_2) \lor (\lnot x_1 \land x_3) \lor (\lnot x_3)$이다.

논리식의 값은 변수에 어떤 값을 넣느냐에 따라 달라진다. 변수마다 값을 정해 주는 함수를 진리 할당이라 하고, $f : \{1, 2, \dots, n\} \to \{\text{참}, \text{거짓}\}$ 꼴로 쓴다. $f(i)$는 변수 $x_i$에 준 값이다. 가능한 진리 할당은 모두 $2^n$가지이고, 할당을 하나 정하면 논리식의 값은 참 아니면 거짓으로 정해진다.

모든 할당에서 값이 참인 논리식을 항진식, 모든 할당에서 값이 거짓인 논리식을 모순식이라 한다. 대부분의 논리식은 둘 중 어느 쪽도 아니어서 값이 할당에 따라 갈린다. 그래서 논리식이 얼마나 참인지를 0 이상 1 이하의 분수로 나타낸다.

$\frac{\text{논리식의 값이 참인 할당의 수}}{2^n}$

이 값이 1이면 항진식이고, 0이면 모순식이다.

예를 들어 $(x_1 \land \lnot x_1) \lor (\lnot x_2 \land \lnot x_3) \lor (x_3 \land x_2)$는 여덟 가지 할당 가운데 네 가지에서 참이므로, 참인 비율이 $1/2$이다.

논리식이 주어지면 참인 비율을 정확히 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$과 $m$이 공백 하나를 사이에 두고 주어진다 ($1 \le n \le 20$, $1 \le m \le 100$). 논리식에 나올 수 있는 변수는 $x_1, x_2, \dots, x_n$이고, 논리식은 절 $m$개로 이루어진다.

이어지는 $m$개의 줄에 절이 한 줄에 하나씩 주어진다. 각 줄은 공백 하나로 구분한 정수로 이루어진다. 줄의 첫 정수 $l$은 그 절을 이루는 리터럴의 개수이며 $1 \le l \le n$이다. 그 뒤에 리터럴을 나타내는 정수 $l$개가 차례로 온다. 이 정수는 모두 0이 아니고 $-n$ 이상 $n$ 이하이다. 정수 $i$는 $x_i$를, 정수 $-i$는 $\lnot x_i$를 뜻한다 ($1 \le i \le n$).

한 절에 같은 변수가 여러 번 나올 수 있고, 어떤 변수와 그 변수의 부정이 한 절에 함께 나올 수도 있다. 변수와 그 부정을 함께 담은 절은 어떤 할당에서도 참이 되지 않는다.

논리식이 참인 비율의 정확한 값을 한 줄에 출력한다. 이 비율은 분모가 $2^n$인 분수이므로 유한소수로 정확히 적을 수 있고, 소수점 아래 자릿수는 많아야 $n$개이다. 소수점 아래 끝의 0은 적지 않는다.

어떤 할당에서도 거짓이면 0을, 모든 할당에서 참이면 1을 출력한다. 나머지 경우에는 답이 0보다 크고 1보다 작으므로 0.으로 시작하는 소수를 출력한다.