题目内容

小华有一个好看的串 $A$。

对于一个串$B$，小华每次可以选择其中任意两个相邻且相同的字符，然后删除其中一个。例如 "aabbbbaa" 可以在一次操作中变成 "abbbbaa" 或 "aabbbaa" 或 "aabbbba"。

如果串 $B$ 可以通过若干次删除操作得到串 $A$，则串 $B$ 也是好看的串。

现在小华得到了一个串 $S$，你需要帮他计算 $S$ 中有多少个子串是好看的串。

两个相等但在字符串 $S$ 中出现位置不同的子串被认为是不同的子串。

解答要求

时间限制：C/C++ 1000ms，其他语言：2000ms
内存限制：C/C++ 256MB，其他语言：512MB

输入描述

第一行两个整数 $n, m$ 表示字符串 $A$ 和 $S$ 的长度 $(1 \le n, m \le 5000)$
第二行一个长度为 $n$ 的字符串 $A$
第三行一个长度为 $m$ 的字符串 $S$

保证字符串仅包含英文小写字母

输出描述

输出一行一个数字表示答案

样例1

输入：

1 1
a
b

输出：

0

解释：

样例2

输入：

3 6
aab
aaabbb

输出：

6

解释：一共 $6$ 个子串

子串 $S[1,3]$: aab
子串 $S[0,3]$: aaab
子串 $S[1,4]$: aabb
子串 $S[0,4]$: aaabb
子串 $S[1,5]$: aabbb
子串 $S[0,5]$: aaabbb