eolymp
bolt
Try our new interface for solving problems
Problems

До первого выпадения Junior

До первого выпадения Junior

Time limit 1 second
Memory limit 256 MiB

Двое игроков играют в следующую игру. Каждый из игроков называет некоторую последовательность, состоящую из 0 и 1. После этого начинают подбрасывать симметричную монету до тех пор, пока результаты последних бросков не совпадут с последовательностью одного из игроков (значение 0 соответствует решке, 1 –гербу). Выигрывает естественно тот игрок, чья последовательность выпадет раньше. Требуется по заданным последовательностям, названным игроками, определить вероятность победы первого игрока.

Ограничения

Последовательности, названные игроками – не пусты и имеют длину не более 10. Ни одна из последовательностей не является суффиксом другой.

Input data

В первой строке содержится последовательность первого игрока, во второй строке – второго игрока (без пробелов).

Output data

Выведите вероятность того, что последовательность первого игрока выпадет раньше, чем последовательность второго игрока с точностью не менее 10^{-8}.

Examples

Input example #1
001
110
Output example #1
0.50000000