精灵正在参加智力游戏。游戏由$$$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}$$$。字符 $$$s_{i, j}$$$ 是 '1' 如果参与者 $$$j$$$ 正确回答问题 $$$i$$$ 或 '0'否则。
输出
打印 Genie 赢得比赛的概率。如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。
示例
输入复制
1 5 11010
输出复制
1.0000000000000000
输入复制
3 3 011 101 110
输出复制
0.3333333333333333
输入复制
6 4 1011 0110 1111 0110 0000 1101
输出复制
0.1666666666666667
注意
在第一个示例中,有一个问题,Genie 将正确回答它,从而赢得游戏(以及参与者 $$$2$$$ 和 $$$4$$$)。
在第二个示例中,一名参与者将在提出第一个问题后离开,另一名参与者将在提出第二个问题后离开。每个参与者获胜的概率为 $$$\frac{1}{3}$$$。