Given a string $S$ that contains lowercase English letters and some number of wildcards '', where '' can be replaced by any string, including an empty string. For a string consisting only of lowercase English letters, if all wildcards in $S$ can be replaced in some way such that the resulting string is exactly equal to that string, then we say that the string can be generated by $S$.

Given another string $T$ consisting only of lowercase English letters, find how many contiguous substrings of $T$ can be generated by $S$ (excluding empty strings).

Input

The first line contains a string $S$ consisting of lowercase English letters and wildcards '' ($1 \le |S| \le 5 \times 10^5$), where the number of '' does not exceed 10.

The second line contains a string $T$ consisting of lowercase English letters ($1 \le |T| \le 5 \times 10^5$).

Output

Output a single integer representing the number of contiguous substrings of $T$ that can be generated by $S$ (excluding empty strings).

Examples

Input 1

c*c*p*c
cccpppccc

Output 1

6

Input 2

**
hello

Output 2

15

Note

In the first example, the 6 contiguous substrings that can be generated are $T_{1..7}, T_{1..8}, T_{1..9}, T_{2..7}, T_{2..8}, T_{2..9}$.