字典树

字符串的异或结果为0，则其串中1的个数必为偶数。

对于$A$中的每个长度为$n$的子串，需要判断该串是否出现过，可以使用哈希来判重，也可以将所有子串扔到字典树(Trie)树上，这样树上从根节点到叶节点的每一条路径，都是独一无二的。

在添加进Trie树时，统计1的个数并进行答案统计即可。

在获取所有子串时，需要对比$A$和$B$。

题目描述

$\qquad$小红拥有两个仅由0和1组成的字符串A，B，其中A的长度为$m$，B的长度为$n$，字符串下标都从$0$开始。现在小红定义了一种字符串生成模式：

$\qquad$（1）从字符串A中选择一个下标$i$，其中$0 \le i \le m-n$；

$\qquad$（2）从下标$i$开始，获取字符串A一个长度为$n$的连续子串；

$\qquad$（3）将取出的子串各字符依次与字符串B中各字符作异或运算，最终生成一个字符串。

$\qquad$例如，字符串A为10101，字符串B为01，则当$i=0$时，生成的字符串为$11$。当$i=1$时，生成的字符串为$00$。

$\qquad$现在定义生成的字符串合法条件为，当且仅当生成的字符串各个字符异或的结果为$0$，更正规的，假设合法的生成的字符串为$S$，S的长度恒等于$n$，对于所有$0 \le i \lt n$，有S[0]^S[1]^...^S[n-1]=0。比如上面的例子中，生成的两个字符串都是合法的。

$\qquad$现在小红想问你，对于给定的字符串A和B，一共有多少种不同的子串可以生成合法的串？

$\qquad$定义两个字符串不同，当对两个串相同下标对应的字符不同，即为字符串不同，例如字符串$10$和$01$不相同。

输入描述

$\qquad$第一行输入两个整数$m$和$n$，分别表示字符串A和B的长度。其中$1 \le n \le m \le 5000$

$\qquad$第二行输入字符串A，第三行输入字符串B。

输出描述

$\qquad$输出一个整数，表示不同的子串个数。

样例

输入

8 2
10100000
01

输出

2

输出解释

用子串10和01生成串合法串11和00，两个用于生成的子串10和01互不相同，所以结果为2。

Limitation

1s, 1024KiB for each test case.