Background

Little L has recently been obsessed with using Google’s “shengcao” generator to create all kinds of weird stuff.

After producing many different works, Little L began to think about the following problem.

Problem Description

Note: For convenience, in the following, all strings are 1-indexed, i.e., positions start from $1$.

Little L treats the original text before each “shengcao” and the resulting text after “shengcao” as two strings $A$ and $B$, both consisting only of lowercase letters.

We define a “partition sequence” and “partition substrings” as follows:

• For a string of length $n$, a “partition sequence” is defined as: there exists a sequence $p$ of length $k+2$ such that $0=p_0<p_1<p_2<...<p_k<p_{k+1}=n+1$. For a partition sequence, its “partition substrings” are the substrings formed by the characters from position $p_i+1$ to $p_{i+1}-1$ ($i \in[0,k]$, possibly the empty string). Clearly, for a partition sequence of length $k+2$, there are $k+1$ partition substrings in total.

• For the same string, two partition sequences ($p$ and $q$) are different if and only if their lengths are different ($k_1\neq k_2$), or there exists an $i$ such that $p_i\neq q_i$.

Different people may understand the same original text and result in different ways. We define one way of understanding as follows:

• For strings $A$ and $B$, we choose one partition sequence for each of them ($p$ and $q$). These two partition sequences must satisfy:

1. The two partition sequences have the same length ($k_1=k_2$).
2. For any $i$, we have $A[p_i]=B[q_i]$, i.e., the character at position $p_i$ in $A$ is the same as the character at position $q_i$ in $B$.

• Define the “shengcao level” of this way of understanding as the sum of squares of the lengths of all partition substrings of the two strings, i.e., $\sum\limits_{i=0}^{k_1}(p_{i+1}-p_i-1)^2+\sum\limits_{i=0}^{k_2}(q_{i+1}-q_i-1)^2$.

• Two ways of understanding are different if and only if their $p$ are different, or their $q$ are different.

Little L wants to know the sum of the shengcao levels over all ways of understanding. Since he does not like the number $10^9+7$, he does not want you to tell him the result as that number, so you need to take the result modulo $10^9+7$.

Input Format

The first line contains two positive integers $n,m$, which are the lengths of $A$ and $B$.

The next line contains a string of length $n$, representing string $A$.

The next line contains a string of length $m$, representing string $B$.

Output Format

One line containing one integer, the answer modulo $10^9+7$.

3 4
abc
bacb

74

7 9
adcbbde
bdaegbcba

2128

Hint

For sample 1, there are the following ways of understanding:

• $p=\{0,4\},q=\{0,5\}$, the shengcao level is $25$.
• $p=\{0,1,4\},q=\{0,2,5\}$, the shengcao level is $9$.
• $p=\{0,2,4\},q=\{0,1,5\}$, the shengcao level is $11$.
• $p=\{0,2,4\},q=\{0,4,5\}$, the shengcao level is $11$.
• $p=\{0,3,4\},q=\{0,3,5\}$, the shengcao level is $9$.
• $p=\{0,1,2,4\},q=\{0,2,4,5\}$, the shengcao level is $3$.
• $p=\{0,1,3,4\},q=\{0,2,3,5\}$, the shengcao level is $3$.
• $p=\{0,2,3,4\},q=\{0,1,3,5\}$, the shengcao level is $3$.

The total shengcao level is $74$.

Constraints

This problem uses bundled testdata.

• Subtask 1( $20\%$ ): $n,m\leq 50$.
• Subtask 2( $30\%$ ): $n,m\leq 200$.
• Subtask 3( $50\%$ ): no special constraints.

For $100\%$ of the data, $n,m\leq 3000$, and $A$ and $B$ contain only lowercase letters.

Translated by ChatGPT 5