题目描述

对于一对字符串 $(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$ 的分数。

样例

10 2
ccbccbbcbb bc

4

20 2
cbcaacabcbacbbabacca ba

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$
  $3$	$5 \times 10 ^ 3$	$20$
  $4$	$4 \times 10 ^ 5$	$30$
  $5$	$3 \times 10 ^ 6$	$20$