E. Межгалактические путешествия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Не так давно учёные открыли кротовые норы — объекты в космосе, позволяющие перемещаться на очень большие расстояния между галактиками и звёздными системами.

Учёным известно, что в пределах досягаемости находятся n галактик. Вы находитесь в галактике 1, и вам нужно попасть в галактику n. Чтобы попасть из галактики i в галактику j, необходимо залететь внутрь кротовой норы (i, j), и спустя ровно одни галактические сутки вы окажетесь в галактике j.

К сожалению, нужная кротовая нора найдётся не всегда. Каждые галактические сутки они исчезают и появляются случайным образом. Однако в пределах одних галактических суток состояние кротовых нор не изменяется. Кротовая нора из галактики i в галактику j существует в каждые отдельно взятые галактические сутки с вероятностью pij. Вы всегда можете узнать, какие кротовые норы существуют в настоящий момент. В каждый момент времени вы можете либо перелететь в другую галактику через одну из существующих в этот момент кротовых нор, либо можете просто ждать одни галактические сутки, чтобы посмотреть, какие норы из вашей текущей позиции будут существовать на следующие сутки.

Требуется найти математическое ожидание времени пути из галактики 1 в галактику n, если вы будете действовать оптимально. Гарантируется, что это математическое ожидание существует.

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

В первой строке записано целое число n (1 ≤ n ≤ 1000) — количество галактик в пределах досягаемости.

Далее записана матрица из n строк и n столбцов. Каждый её элемент pij обозначает вероятность существования кротовой норы из галактики i в галактику j. Все вероятности даны в процентах и представляют собой целые числа. Гарантируется, что все элементы на главной диагонали равны 100.

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

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

А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если .

Примеры
Входные данные
3
100 50 50
0 100 80
0 0 100
Выходные данные
1.750000000000000
Входные данные
2
100 30
40 100
Выходные данные
3.333333333333333
Примечание

Комментарий ко второму примеру: каждые галактические сутки с вероятностью 0.3 появится кротовая нора прямо до точки назначения. Поэтому время достижения финиша — это ожидаемое число экспериментов до ближайшей реализации случайного события с вероятностью 0.3, т.е. .