Гра запитань#11326

Гра запитань

3 секунди

512 мегабайтів

Легка

Джин бере участь в інтелектуальній грі. Гра складається з $n$ питань, і в ній бере участь $m$ учасників, пронумерованих від $1$ до $m$ . Джин — учасник під номером $1$ .

Для кожного питання $i$ і учасника $j$ відомо, чи відповість учасник на питання правильно чи ні.

Мета гри — залишитися останнім учасником, що залишився в грі.

Гра проводиться наступним чином. Спочатку всі $n$ питань перемішуються випадковим чином (усі перестановки $n!$ рівноймовірні). Потім питання задаються одне за одним. Кожен учасник відповідає на питання. Якщо всі учасники, що ще в грі, відповідають на питання правильно або якщо всі вони відповідають неправильно, нічого не відбувається. В іншому випадку ті учасники, які відповідають на питання неправильно, програють і вибувають з гри.

Після того, як будуть задані всі $n$ питань, усі учасники, що залишилися в грі, оголошуються переможцями.

Яка ймовірність того, що Джин виграє гру?

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m (1 \leq n \leq 2 \cdot 1 0^{5}, 2 \leq m \leq 17)$ m~(1 \le n \le 2 \cdot 10^5, 2 \le m \le 17) — кількість питань і кількість учасників.

$i$ -й з наступних $n$ рядків містить $m$ символів $s_{i, 1}, s_{i, 2}, ..., s_{i, m}$ s_{i,1}, s_{i,2}, ..., s_{i,m}. Символ $s_{i, j}$ s_{i,j} дорівнює $1$ , якщо учасник $j$ правильно відповів на питання $i$ , або $0$ інакше.

Вихідні дані

Виведіть ймовірність того, що Джин виграє гру. Ваша відповідь буде вважатися правильною, якщо її абсолютна або відносна похибка не перевищує $1 0^{- 9}$ 10^{-9}.

Приклади

У першому прикладі є одне питання, і Джин відповість на нього правильно, тим самим вигравши гру (разом з учасниками $2$ і $4$ ).

У другому прикладі один учасник піде після першого заданого питання, а інший учасник піде після другого заданого питання. Кожен учасник виграє з ймовірністю $1/3$ .

Приклад 1

Приклад 2

Приклад 3