「TAOI-2」Ciallo～(∠・ω< )⌒★

题目背景

柚子厨差不多得了。 ~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<) ![](https://cdn.luogu.com.cn/upload/image_hosting/0nqiwonz.png)

题目描述

小 δ 喜欢造词。他学习了一种造词方法。 首先，他拥有一个「模板串」，设为 $s$。然后他会选择一对 $1 \le l \le r \le |s|$，将 $s$ 的第 $l$ 至 $r$ 个字符删掉，把两边的字符串拼起来，他设得到的这个新字符串为 $s'$。 接下来，他会选择一对新的 $1 \le l' \le r' \le |s'|$，然后设 $s'$ 的第 $l'$ 至 $r'$ 个字符组成的字符串为 $s''$。他所造出的这个词就是 $s''$。 例如，如果「模板串」为 $s=\texttt{cciaohalloo}$，那么一种造词方法是，选择 $l=5$，$r=7$，得到 $s'=\texttt{ccialloo}$，然后选择 $l'=2$，$r'=7$，得到 $s''=\texttt{ciallo}$。 现在小 δ 有一个「目标串」 $t$，他想知道有多少种不同的方案，可以使用「模板串」$s$ 造出单词 $t$。定义两种方案相同当且仅当选择的 $l,r,l',r'$ 均相同。

输入输出格式

输入格式


共两行，分别为字符串 $s$ 和 $t$。

输出格式


共一行，代表造出「目标串」$t$ 的方案数。

输入输出样例

输入样例 #1

aabbaaba
aba

输出样例 #1

23

输入样例 #2

ciaohallo
ciallo

输出样例 #2

2

输入样例 #3

babacbbaababbacbababbabbbaaabaabababbabbabababba
ababab

输出样例 #3

1535

输入样例 #4

sssssssssssssssssssssssssssssssssssss
sss

输出样例 #4

15470

输入样例 #5

abcbbbcbcbcbacbacbaaabcbcbcbaabacbca
cb

输出样例 #5

3995

说明

### 数据范围 **本题采用捆绑测试**。 - 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）：无特殊限制。 对于所有测试数据，$1 \le |s| \le 4 \times 10^5$，$1 \le |t| \le 2 \times 10^5$。$s,t$ 只包含小写英文字母。