To the First Junior Fall#4564
Two players are engaged in a game where each selects a sequence made up of s and s. A fair coin is then flipped repeatedly until the outcomes of the most recent flips match one of the players' sequences ( represents tails, 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 . 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 (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