To the first fall of High#4563
Two players are engaged in a game where each selects a sequence composed of s and s. A fair coin is then tossed repeatedly, with representing tails and 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 . Neither sequence is a suffix of the other.
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 the probability that the first player's sequence appears before the second player's sequence, with a precision of at least 10^{-8}.
Example 1