Problem Description
You are given two strings s, and t. Count the number of substrings of s that contain t as a subsequence at least once.
Note that a substring and a subsequence both consist of characters from the original string, in order. In a substring, the characters must be contiguous in the original string, but in a subsequence, they are not required to be contiguous. In the string abcde, ace is a subsequence but not a substring.
If s is aa and t is a, then the answer is 3: [a]a, [aa], and a[a].
Input
Each test case will consist of exactly two lines. The first line will contain string s (1≤|s|≤105,s∈[a−z]∗), with no other characters.
The second line will contain string t (1≤|t|≤100,|t|≤|s|,t∈[a−z]∗), with no other characters.
Output
Output a single integer, which is the number of substrings of s that contain t as a subsequence at least once.
Samples
Sample Input 1
abcdefghijklmnopqrstuvwxyz
a
Sample Output 1
26
Sample Input 2
abcdefghijklmnopqrstuvwxyz
m
Sample Output 2
182