До першого випадіння High#4563
Двоє гравців грають у наступну гру. Кожен з гравців називає деяку послідовність, яка складається з та . Після цього починають підкидувати симетричну монету до тих пір, доки результати останніх кидань не співпадуть з послідовністю одного з гравців (значення відповідає решці, – гербу). Виграє звичайно той гравець, чия послідовність випаде раніше. Потрібно за заданими послідовностями, названими гравцями, визначити ймовірність перемоги першого гравця.
Обмеження
Послідовності, названі гравцями – не порожні і мають довжину не більшу . Жодна з послідовностей не є суфіксом іншої.
У першому рядку міститься послідовність першого гравця, у другому рядку – другого гравця (без пропусків).
Виведіть ймовірність того, що послідовність першого гравця випаде раніше, ніж послідовність другого гравця з точністю не менше 10^{-8}.
Приклад 1