2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

combinatorics

dp

fft

math

probabilities

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Game of Questions

time limit per test

5 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard 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?

Input

The 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.

Output

Print 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}$$$.

Examples

Input

1 5 11010

Output

1.0000000000000000

Input

3 3 011 101 110

Output

0.3333333333333333

Input

6 4 1011 0110 1111 0110 0000 1101

Output

0.1666666666666667

Note

In 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}$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/04/2023 09:06:41 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|