E. Очередной турнир ситхов
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Всем известны правила турнира ситхов. В турнире сражаются n участников. Турнир начинается со случайного выбора двух ситхов, который проводят первый бой. Как только один из них проигрывает, его место занимает другой, случайно выбранный еще не сражавшийся ситх. Надо ли говорить, что каждый бой турнира ситхов заканчивается смертью одного из соперников? Турнир заканчивается, когда в живых остается лишь один ситх.

Джедай Иван случайно оказался в списке участников такого турнира. Однако его владение светлой стороной силы столь велико, что он способен влиять на исход выбора как участников, которые начнут турнир, так и каждого следующего участника поединка. Разумеется, он не станет упускать подвернувшийся шанс улучшить свое положение. Помогите ему рассчитать, насколько велики его шансы победить в турнире.

Входные данные

В первой строке записано единственное число n (1 ≤ n ≤ 18) — количество участников турнира ситхов.

В каждой из следующих n строк записано n вещественных чисел, образующих матрицу pij (0 ≤ pij ≤ 1). Каждый ее элемент pij равен вероятности того, что i-й участник победит j-го в поединке один на один.

Элементы на главной диагонали pii равны нулю. Для любых различных i, j выполняется pij + pji = 1. Все вероятности указаны не более чем с шестью знаками после запятой.

Джедай Иван находится в списке участников под номером 1.

Выходные данные

Выведите единственное вещественное число — вероятность, с которой Джедай Иван останется в живых по итогам турнира. Абсолютная или относительная погрешность ответа не должна превышать 10 - 6.

Примеры
Входные данные
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0
Выходные данные
0.680000000000000