题目内容

有一个字符串 $A$，并将其称为“好看串”。

对于任意字符串 $B$，可以反复执行以下操作：选择 $B$ 中两个相邻且相同的字符，删除其中一个。如果 $B$ 能够通过若干次（包括 $0$ 次）这样的操作变成 $A$，则称 $B$ 也是“好看串”。

现在给定一个字符串 $S$。$S$ 的一个子串定义为 $S$ 中连续的一段字符。请你计算 $S$ 中有多少个子串是“好看串”。

如果两个子串在 $S$ 中的出现位置不同，即使它们的内容完全相同，也视为不同的子串。

约束条件：

• 字符串 $A$ 与字符串 $S$ 的长度 $n$ 和 $m$ 满足 $1 \le n,m \le 5000$。
• 两个字符串均只包含英文小写字母。

输入描述

输入共三行。

第一行包含两个整数 $n$ 和 $m$，依次表示字符串 $A$ 与字符串 $S$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $A$。

第三行包含一个长度为 $m$ 的字符串 $S$。

输出描述

输出一个整数，表示 $S$ 中子串中“好看串”的数量。

样例1

输入

3 5
aaa
aaaaa

输出

6

说明

好看串共有以下 6 个：

• S[1..3] = aaa
• S[2..4] = aaa
• S[3..5] = aaa
• S[1..4] = aaaa
• S[2..5] = aaaa
• S[1..5] = aaaaa

样例2

输入

3 7
aba
aaabbaa

输出

6

说明

好看串共有以下 6 个：

• S[1..6] = aaabba
• S[1..7] = aaabbaa
• S[2..6] = aabba
• S[2..7] = aabbaa
• S[3..6] = abba
• S[3..7] = abbaa

样例3

输入

1 1
a
b

输出

0

说明

$A$ 是单个字符 a，而 $S$ 的唯一子串是 b。

由于 b 无法通过删除相邻相同字符变成 a，也没有其他子串可选，因此好看子串数量为 0。