[JLOI2011] 基因补全

题目描述

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

输入格式

数据包括三行。 第一行有两个整数$n$，$m$，表示碱基序列的长度。 第二行包含$n$个字符，表示碱基序列$S$。 第三行包含$m$个字符，表示碱基序列$T$。 两个碱基序列的字符种类只有$A,C,G,T$这$4$个大写字母。

输出格式

答案只包含一行，表示补全方案的个数。

样例 #1

样例输入 #1

10 3
CTAGTAGAAG
TCC

样例输出 #1

4

提示

样例解释： $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$