Гра запитань

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

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

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

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

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

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

Вхідні дані

Перша рядок містить два цілих числа $n$ і $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,j}$ дорівнює $1$, якщо учасник $j$ правильно відповів на питання $i$, або $0$ інакше.

Вихідні дані

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

Приклади

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

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