P5484 [JLOI2011] Gene Completion

In biology class, we learned that bases make up $DNA$ (deoxyribonucleic acid). They can be represented by the uppercase letters $A, C, T, G$, where $A$ always pairs with $T$, and $C$ always pairs with $G$. Two base sequences can match each other if and only if they have the same length, and at every position, the two bases can pair with each other. For example, $ACGTC$ can and only can pair with $TGCAG$. A relatively shorter base sequence can be made to pair with a relatively longer base sequence by inserting bases at any positions in the shorter sequence. Different insertion positions or different numbers of inserted bases are considered different completion plans. Now you are given two base sequences $S$ and $T$, with lengths $n$ and $m$ respectively ($n \geq m$). Find how many completion plans there are in total.

The input has three lines. The first line contains two integers $n$ and $m$, representing the lengths of the base sequences. The second line contains $n$ characters, representing the base sequence $S$. The third line contains $m$ characters, representing the base sequence $T$. The characters in both sequences are only the $4$ uppercase letters $A, C, G, T$.

Output one line containing the number of completion plans.

Sample explanation: The $4$ completion plans for $TCC$ (characters in parentheses are the inserted bases): $(GA)TC(AT)C(TTC)$ $(GA)TC(ATCTT)C$ $(GA)T(CAT)C(TT)C$ $(GATCA)TC(TT)C$ Constraints: For $30\%$ of the testdata, $n \leq 1000, m \leq 2$. For $50\%$ of the testdata, $n \leq 1000, m \leq 4$. For $100\%$ of the testdata, $n \leq 2000, m \leq n$. Translated by ChatGPT 5