Problem Description

For a pair of strings $(s_1, s_2)$, for every substring $[l, r]$ of $s_1$ with odd length, if $[l, r]$ is a palindrome, then the “score” of $s_1$ increases by the number of occurrences of $s_2$ inside $[l, r]$.

Now you are given a pair $(s_1, s_2)$. Please compute the “score” of $s_1$.

Output the answer modulo $2 ^ {32}$.

Input Format

The first line contains two integers $n, m$, representing the lengths of $s_1$ and $s_2$.

The second line contains two strings $s_1, s_2$.

Output Format

Output one integer on a single line, representing the score of $s_1$.

10 2
ccbccbbcbb bc

4

20 2
cbcaacabcbacbbabacca ba

4

Hint

Sample Explanation

For sample 1:

$s_2$ appears once in the substring $[1, 5]$, and once in the substring $[2, 4]$.

$s_2$ appears once in the substring $[7, 9]$, and once in the substring $[6, 10]$.

Constraints

This problem uses bundled testdata.

• For $100\%$ of the testdata: $1 \le n, m \le 3 \times 10 ^ 6$, and all characters in the strings are lowercase letters.

• Detailed constraints:

  Subtask ID	$n, m \le$	Points
  $1$	$100$	$15$
  $2$	$10 ^ 3$
  $3$	$5 \times 10 ^ 3$	$20$
  $4$	$4 \times 10 ^ 5$	$30$
  $5$	$3 \times 10 ^ 6$	$20$

Translated by ChatGPT 5