题目描述

Genie 正在参加一个智力游戏。游戏包含 $n$ 个问题，有 $m$ 名从 $1$ 到 $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}$。如果参赛者 $j$ 正确回答了问题 $i$，则字符 $s_{i, j}$ 为 $\tt{1}$，否则为 $\tt{0}$。

输出格式

输出 Genie 赢得游戏的概率。如果你的答案的绝对或相对误差不超过 $10^{-9}$，则该答案将被认为是正确的。

输入输出样例 #1

输入 #1

1 5
11010

输出 #1

1.0000000000000000

输入输出样例 #2

输入 #2

3 3
011
101
110

输出 #2

0.3333333333333333

输入输出样例 #3

输入 #3

6 4
1011
0110
1111
0110
0000
1101

输出 #3

0.1666666666666667

说明/提示

在第一个样例中，只有一个问题，Genie 会正确回答，因此赢得比赛（与参赛者 $2$ 和 $4$ 一起）。

在第二个样例中，一名参赛者将在第一个被问到的问题后离开，另一名参赛者将在第二个被问到的问题后离开。每位参赛者获胜的概率为 $\frac{1}{3}$。

翻译由 gemini2.5pro 完成