回文匹配
题目描述
对于一对字符串 $(s_1,s_2)$，若 $s_1$ 的长度为奇数的子串 $(l,r)$ 满足 $(l,r)$ 是回文的，那么 $s_1$ 的“分数”会增加 $s_2$ 在 $(l,r)$ 中出现的次数。
现在给出一对 $(s_1,s_2)$，请计算出 $s_1$ 的“分数”。
答案对 $2 ^ {32}$ 取模。
输入输出格式
输入格式
第一行两个整数，$n,m$，表示 $s_1$ 的长度和 $s_2$ 的长度。
第二行两个字符串，$s_1,s_2$。
输出格式
一行一个整数，表示 $s_1$ 的分数。
输入输出样例
输入样例 #1
10 2
ccbccbbcbb bc输出样例 #1
4输入样例 #2
20 2
cbcaacabcbacbbabacca ba
输出样例 #2
4
说明
**【样例解释】**
对于样例一：
子串 $(1,5)$ 中 $s_2$ 出现了一次，子串 $(2,4)$ 中 $s_2$ 出现了一次。
子串 $(7,9)$ 中 $s_2$ 出现了一次，子串 $(6,10)$ 中 $s_2$ 出现了一次。
--------------------------------------
**【数据范围】**
**本题采用捆绑测试。**
- 对于 $100\%$ 的数据：$1 \le n,m \le 3 \times 10 ^ 6$，字符串中的字符都是小写字母。
- **详细的数据范围：**
| Subtask 编号 | $n,m \le$ | 分值 |
| :----------: | :---------------: | :--: |
| $1$ | $100$ | $15$ |
| $2$ | $10 ^ 3$ | $15$ |
| $3$ | $5 \times 10 ^ 3$ | $20$ |
| $4$ | $4 \times 10 ^ 5$ | $30$ |
| $5$ | $3 \times 10 ^ 6$ | $20$ |