P6693 Google "Shengcao" Translator

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.

**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

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$.

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

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