Не так давно учёные открыли кротовые норы — объекты в космосе, позволяющие перемещаться на очень большие расстояния между галактиками и звёздными системами.
Учёным известно, что в пределах досягаемости находятся n галактик. Вы находитесь в галактике 1, и вам нужно попасть в галактику n. Чтобы попасть из галактики i в галактику j, необходимо залететь внутрь кротовой норы (i, j), и спустя ровно одни галактические сутки вы окажетесь в галактике j.
К сожалению, нужная кротовая нора найдётся не всегда. Каждые галактические сутки они исчезают и появляются случайным образом. Однако в пределах одних галактических суток состояние кротовых нор не изменяется. Кротовая нора из галактики i в галактику j существует в каждые отдельно взятые галактические сутки с вероятностью pij. Вы всегда можете узнать, какие кротовые норы существуют в настоящий момент. В каждый момент времени вы можете либо перелететь в другую галактику через одну из существующих в этот момент кротовых нор, либо можете просто ждать одни галактические сутки, чтобы посмотреть, какие норы из вашей текущей позиции будут существовать на следующие сутки.
Требуется найти математическое ожидание времени пути из галактики 1 в галактику n, если вы будете действовать оптимально. Гарантируется, что это математическое ожидание существует.
Выходные данные
Выведите единственное вещественное число — математическое ожидание времени пути из галактики 1 в галактику n. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
Примечание
Комментарий ко второму примеру: каждые галактические сутки с вероятностью 0.3 появится кротовая нора прямо до точки назначения. Поэтому время достижения финиша — это ожидаемое число экспериментов до ближайшей реализации случайного события с вероятностью 0.3, т.е. 
.