До первого выпадения High
Двое игроков играют в следующую игру. Каждый из игроков называет некоторую последовательность, состоящую из 0 и 1. После этого начинают подбрасывать симметричную монету до тех пор, пока результаты последних бросков не совпадут с последовательностью одного из игроков (значение 0 соответствует решке, 1 – гербу). Выигрывает естественно тот игрок, чья последовательность выпадет раньше. Требуется по заданным последовательностям, названным игроками, определить вероятность победы первого игрока.
Ограничения
Последовательности, названные игроками – не пусты и имеют длину не более 50. Ни одна из последовательностей не является суффиксом другой.
Входные данные
В первой строке содержится последовательность первого игрока, во второй строке – второго игрока (без пробелов).
Выходные данные
Выведите вероятность того, что последовательность первого игрока выпадет раньше, чем последовательность второго игрока с точностью не менее 10^{-8}.