To the First Junior Fall
Two players are engaged in a game where each selects a sequence made up of 0s and 1s. A fair coin is then flipped repeatedly until the outcomes of the most recent flips match one of the players' sequences (0 represents tails, 1 represents heads). The player whose sequence appears first in the sequence of coin flips wins. 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 10. - 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 (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}.