G. Game of Questionstime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputGenie is taking part in an intellectual game. The game consists of $$$n$$$ questions, and there are $$$m$$$ participants numbered from $$$1$$$ to $$$m$$$. Genie is the participant number $$$1$$$.For each question $$$i$$$ and participant $$$j$$$, it is known whether the participant will answer the question correctly or not.The goal of the game is to be the last participant staying in the game.The game is conducted as follows. First, all $$$n$$$ questions get shuffled uniformly at random (all $$$n!$$$ permutations are equally likely). Then, the questions are asked one by one. Each participant answers the question. If all participants still in the game answer the question correctly, or if all of them answer the question incorrectly, nothing happens. Otherwise, those participants who answer the question incorrectly lose and leave the game.After all $$$n$$$ questions are asked, all participants who are still in the game are declared to be the winners.What is the probability that Genie will win the game?InputThe first line contains two integers $$$n$$$ and $$$m$$$ — the number of questions and the number of participants ($$$1 \le n \le 2 \cdot 10^5$$$; $$$2 \le m \le 17$$$).The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ characters $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, m}$$$. Character $$$s_{i, j}$$$ is '1' if participant $$$j$$$ answers question $$$i$$$ correctly or '0' otherwise.OutputPrint the probability that Genie will win the game. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-9}$$$.ExamplesInput1 5
11010
Output1.0000000000000000
Input3 3
011
101
110
Output0.3333333333333333
Input6 4
1011
0110
1111
0110
0000
1101
Output0.1666666666666667
NoteIn the first example, there is a single question and Genie will answer it correctly, thus winning the game (along with participants $$$2$$$ and $$$4$$$).In the second example, one participant will leave after the first asked question, and another participant will leave after the second asked question. Each participant will win with probability $$$\frac{1}{3}$$$.