Game of Questions

Genie는 지적 게임에 참가하고 있다. 이 게임은 $n$개의 문제로 이루어지며, $1$번부터 $m$번까지 번호가 매겨진 $m$명의 참가자가 있다. Genie는 $1$번 참가자이다.

각 문제 $i$와 참가자 $j$에 대해, 참가자가 그 문제를 맞힐지 틀릴지가 주어진다.

게임의 목표는 끝까지 남아 있는 마지막 참가자가 되는 것이다.

게임은 다음과 같이 진행된다. 먼저 $n$개의 문제를 균일한 확률로 무작위로 섞는다(가능한 $n!$개의 순열이 모두 같은 확률을 가진다). 그다음 문제를 하나씩 출제한다. 각 참가자가 그 문제에 답한다. 아직 남아 있는 참가자가 모두 맞히거나 모두 틀리면 아무 일도 일어나지 않는다. 그렇지 않으면 틀린 참가자가 탈락한다.

$n$개의 문제를 모두 출제한 뒤 아직 남아 있는 참가자는 모두 승자로 선언된다.

Genie가 게임에서 이길 확률은 얼마인가?

첫 줄에 문제 수 $n$과 참가자 수 $m$이 주어진다($1 \le n \le 2 \cdot 10^5$; $2 \le m \le 17$).

이어지는 $n$개의 줄 중 $i$번째 줄에는 $m$개의 문자 $s_{i,1}, s_{i,2}, \ldots, s_{i,m}$이 주어진다. 문자 $s_{i,j}$는 참가자 $j$가 문제 $i$를 맞히면 '1', 그렇지 않으면 '0'이다.

Genie가 게임에서 이길 확률을 출력한다. 절대 오차 또는 상대 오차가 $10^{-9}$ 이하이면 정답으로 인정한다.