P5484 [JLOI2011] 基因补全

在生物课中我们学过，碱基组成了$DNA$（脱氧核糖核酸），他们分别可以用大写字母$A,C,T,G$表示，其中$A$总与$T$配对，$C$总与$G$配对。两个碱基序列能相互匹配，当且仅当它们等长，并且任意相同位置的碱基都是能相互配对的。例如$ACGTC$能且仅能与$TGCAG$配对。一个相对短的碱基序列能通过往该序列中任意位置补足碱基来与一个相对长的碱基序列配对。补全碱基的位置、数量不同，都将视为不同的补全方案。现在有两串碱基序列$S$和$T$，分别有$n$和$m$个碱基($n\geq m$)，问一共有多少种补全方案。

无

无

样例解释： $TCC$的$4$种补全方案（括号中字符为补全的碱基） $(GA)TC(AT)C(TTC)$ $(GA)TC(ATCTT)C$ $(GA)T(CAT)C(TT)C$ $(GATCA)TC(TT)C$ 数据范围： 对于$30\% $数据，$n\leq 1000,m\leq 2$ 对于$50\% $数据，$n\leq 1000,m\leq 4$ 对于$100\% $数据，$n\leq 2000,m\leq n$