AT_abc452_d [ABC452D] No-Subsequence Substring

You are given strings $ S $ and $ T $ consisting of lowercase English letters. Among the non-empty substrings $ s $ of $ S $ , count those that do **not** contain $ T $ as a (not necessarily contiguous) subsequence. Here, two substrings of $ S $ are distinguished if they are taken from different positions, even if they are equal as strings. What is a substring? A substring of a string $ X $ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $ X $ . What is a subsequence? A subsequence of a string $ X $ is a string obtained by deleting zero or more elements from $ X $ and arranging the remaining elements in their original order.

The input is given from Standard Input in the following format: > $ S $ $ T $

Output the answer.

### Sample Explanation 1 For example, the substring `abr` consisting of the first through third characters of $ S $ does not contain $ T $ as a subsequence. Including this, there are $ 51 $ substrings satisfying the condition, such as `k` (only the fifth character of $ S $ ) and `akada` (the fourth through eighth characters of $ S $ ). Note that the string `abr` can be obtained both as the substring from the first to third characters of $ S $ and as the substring from the eighth to tenth characters of $ S $ , but they are taken from different positions, so they are counted separately. ### Sample Explanation 2 All non-empty substrings of $ S $ contain $ T $ as a subsequence. Thus, there are no substrings satisfying the condition, so output $ 0 $ . ### Constraints - $ S $ is a string consisting of lowercase English letters. - $ 1\le |S|\le2\times10 ^ 5 $ , where $ |S| $ is the length of $ S $ . - $ T $ is a string consisting of lowercase English letters. - $ 1\le |T|\le50 $ , where $ |T| $ is the length of $ T $ .