To the first fall of High
Two players are engaged in a game where each selects a sequence composed of 0s and 1s. A fair coin is then tossed repeatedly, with 0 representing tails and 1 representing heads, until the sequence of tosses matches one of the players' sequences. The player whose sequence appears first is declared the winner. Your task is to calculate the probability that the first player's sequence appears before the second player's sequence.
Constraints
- The sequences chosen by the players are non-empty and have a maximum length of 50. - Neither sequence is a suffix of the other.
Input
The input consists of two lines: the first line contains the sequence of the first player, and the second line contains the sequence of the second player, both without spaces.
Output
Output the probability that the first player's sequence appears before the second player's sequence, with a precision of at least 10^{-8}.