Problem Description

Little δ enjoys creating words. He has learned a method to create words.

First, he has a "template string" denoted as $s$. Then he will choose a pair $1 \le l \le r \le |s|$, delete the characters from the $l$-th to the $r$-th of $s$, and concatenate the remaining parts of the string. He denotes this new string as $s'$.

Next, he will choose a new pair $1 \le l' \le r' \le |s'|$, and denote the substring from the $l'$-th to the $r'$-th character of $s'$ as $s''$. The word he creates is $s''$.

For example, if the "template string" is $s=\texttt{cciaohalloo}$, one way to create a word is to choose $l=5$, $r=7$, resulting in $s'=\texttt{ccialloo}$, and then choose $l'=2$, $r'=7$, resulting in $s''=\texttt{ciallo}$.

Now, Little δ has a "target string" $t$, and he wants to know how many different ways there are to create the word $t$ using the "template string" $s$. Two schemes are considered the same if and only if the chosen $l, r, l', r'$ are all the same.

Input Format

There are two lines in total, representing the strings $s$ and $t$ respectively.

Output Format

There is one line in total, representing the number of ways to create the "target string" $t$.

Sample Input and Output

Input Sample #1

aabbaaba
aba

Output Sample #1

23

Input Sample #2

ciaohallo
ciallo

Output Sample #2

2

Input Sample #3

babacbbaababbacbababbabbbaaabaabababbabbabababba
ababab

Output Sample #3

1535

Input Sample #4

sssssssssssssssssssssssssssssssssssss
sss

Output Sample #4

15470

Input Sample #5

abcbbbcbcbcbacbacbaaabcbcbcbaabacbca
cb

Output Sample #5

3995

Notes

Data Range

This problem uses batched testing.

• Subtask 0 (6 points): $|s| \le 400$, $|t| \le 200$.
• Subtask 1 (10 points): $|s| \le 700$, $|t| \le 300$.
• Subtask 2 (10 points): $\forall i,j, s_i=t_j$.
• Subtask 3 (10 points): $|t|=1$.
• Subtask 4 (20 points): $|s| \le 10^4$, $|t| \le 3 \times 10^3$.
• Subtask 5 (14 points): $|t|=2$.
• Subtask 6 (30 points): No special restrictions.

For all test cases, $1 \le |s| \le 4 \times 10^5$, $1 \le |t| \le 2 \times 10^5$. $s$ and $t$ only contain lowercase English letters.

见题面 Input 部分

见题面 Output 部分