Problem Description

Takahashi loves stickerless keyboards. Today, he is trying to write a text using a keyboard whose keys do not have any markings for alphabets and numbers.

However, Takahashi does not fully remember the layout of the keyboard. For the characters he remembers, he can press the corresponding keys directly. For the ones he does not remember, he has to guess and press a key, and if it is incorrect, he must delete it using the backspace key.

Takahashi is trying to type the text $ S $. He wants to minimize the expected number of key presses required to type this text. Takahashi can remember which character appeared when he pressed a key and use this information to choose the next key to press.

Calculate the expected number of key presses when Takahashi adopts the optimal strategy to achieve his goal.

Note that the positions of the backspace key and all keys other than alphabets and numbers are assumed to be remembered.

Also, operations that change the input position, such as arrow keys or mouse operations, are not allowed.

Input Format

The input is given from the standard input in the following format:

$ S $ $ K $

• The first line contains the string $S\ (1\ ≦\ |S|\ ≦\ 50)$ that Takahashi wants to type. The string $ S $ is guaranteed to consist only of lowercase alphabets or digits.
• The second line contains the string $ K $ representing the keys that Takahashi remembers. The string $ K $ can be created by arbitrarily removing one or more characters from 1234567890abcdefghijklmnopqrstuvwxyz, and it is guaranteed that the first character is 1.

Output Format

Output the expected number of key presses required for Takahashi to type the text $ S $ in one line. The output should include a newline at the end.

The output will be accepted if the absolute or relative error is within $ 10^{-6} $.

Sample Input and Output

Sample Input #1

takahashikun
1234567890abcdefghijklmnopqrstuvwxyz

Sample Output #1

12

Sample Input #2

p
1234567890abcdefghijklmnorstuvwxyz

Sample Output #2

2

Notes/Hints

Sample Explanation 1

Takahashi remembers all the keys. Therefore, the number of key presses required is the same as the number of characters in takahashikun, which is $ 12 $.

Sample Explanation 2

Takahashi has forgotten the positions of the keys p and q. To type p, he needs to press one of these two unknown keys:
- If he presses p, the text is completed, and the total number of key presses is $ 1 $.
- If he presses q, he will know that the other key is p. He then deletes one character using the backspace key and presses the p key again to complete the text. In this case, the total number of key presses is $ 3 $.
Since both outcomes are equally likely, the expected number of key presses is $ 2 $.

见题面 Input 部分

见题面 Output 部分