P6216 回文匹配

对于一对字符串 $(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,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$ |