题目背景

柚子厨差不多得了。

~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)~(·<)

题目描述

小 δ 喜欢造词。他学习了一种造词方法。

首先，他拥有一个「模板串」，设为 $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$ 的方案数。

aabbaaba
aba

23

ciaohallo
ciallo

2

babacbbaababbacbababbabbbaaabaabababbabbabababba
ababab

1535

sssssssssssssssssssssssssssssssssssss
sss

15470

abcbbbcbcbcbacbacbaaabcbcbcbaabacbca
cb

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$ 只包含小写英文字母。