Subsequences in Substrings

You are given two strings $s$ and $t$. Count the number of substrings of $s$ that contain $t$ as a subsequence at least once.

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. In a subsequence, they do not have to be contiguous. In the string abcde, ace is a subsequence but not a substring.

If $s$ is aa and $t$ is a, the answer is 3: [a]a, [aa], and a[a].

Each test case consists of exactly two lines.

The first line contains string $s$ ($1 \le |s| \le 10^5$, $s \in [a-z]^*$), with no other characters. The second line contains string $t$ ($1 \le |t| \le 100$, $|t| \le |s|$, $t \in [a-z]^*$), with no other characters.

Output a single integer: the number of substrings of $s$ that contain $t$ as a subsequence at least once.