Вы получили в подарок очень умного робота, передвигающегося по прямоугольному полю. К сожалению, робот оказался сломан: он ведет себя как-то странно и передвигается случайным образом. Поле состоит из N строк и M столбцов. Изначально робот находится в клетке на пересечении i-ой строки и j-ого столбца. Далее на каждом шаге робот может пойти на другую клетку. Его цель — попасть на самую нижнюю (N-ую) строку. На каждом шаге робот может остаться на своей текущей клетке, перейти влево, вправо, или вниз на соседнюю клетку. Если робот находится в самом левом столбце, он не может пойти влево, а если он находится в самом правом столбце, он не может пойти вправо. На каждом шаге все возможные действия равновероятны. Найдите математическое ожидание числа шагов, требующихся чтобы дойти до самой нижней строки.
Выходные данные
Выведите математическое ожидание необходимого числа шагов как минимум с 4 знаками после десятичной точки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 10
10 4
|
0.0000000000
|
|
2
|
10 14
5 14
|
18.0038068653
|