题目描述

伊文拥有两个仅由0和1组成的字符串A，B，其中A的长度为m，B的长度为n(m >= n)，字符串下标都从0开始。现在伊文定义了一种字符串生成模式：

1. 从字符串A中选择一个下标i，其中0 <= i <= m - n;
2. 从下标i开始，获取字符串A一个长度为n的连续子串；
3. 将取出的子串各字符依次与字符串B中各字符作异或运算，最终生成一个字符串。

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

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

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

输入描述

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

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

输出描述

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

输入示例

8 2
10100000
01

输出示例

2

提示信息

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

时间限制：c/c++：1s；其他语言：3s。