题目大意：给定一个仅包含01-的字符串，对于每个字符，如果是数字，则放入新字符串的末尾，否则删除新字符串的开头或者结尾，请问有多少种方案可以得到字符串t？
题目描述
Kri 非常喜欢字符串，所以他准备找 $t$ 组字符串研究。
第 $i$ 次研究中，Kri 准备了两个字符串 $S$ 和$R$ ，其中 $S$ 长度为 $n$，且只由 `0`, `1`, `-` 三种字符构成（注：这里的第三种字符是减号），$R$ 初始时为空。
每次研究，Zay 会带着一个美丽的长度为 $m$ 的字符串 $T$ 来找 Kri 玩，Kri 非常羡慕 Zay 拥有如此美丽的字符串，便也想用字符串 $S$ 和 $R$ 变出字符串 $T$。
具体地，Kri 将会进行 $n$ 次操作。每次操作中，Kri 会取出 $S$ 的第一个字符（记为 $c$），并将其从 $S$ 中删去。如果 $c = \texttt{-}$，则 Kri 要删去 $R$ 的开头字符或结尾字符（数据保证删去后 $R$ 不为空）。否则，Kri 会将 $c$ 加入到 $R$ 的末尾。
当进行完所有操作后，Kri 会检查 $R$ 是否和 $T$ 相等。如果 $R = T$，Kri 就会感到开心；否则，Kri 会感到难受。
请问在每次研究中，Kri 有多少种操作方式使自己最后感到开心？我们定义两种方案不同，当且仅当在某种方案的某次操作中， Kri 删去了 $R$ 的开头字符。而在另一种方案的这次操作中， Kri 删去了 $R$ 的结尾字符。
由于答案可能很大，你只需要输出答案除以 $1,000,000,007$（即 $10^9+7$）的余数。
输入输出格式
输入格式
第一行一个正整数 $t$。
接下来有 $t$ 组数据分别表示 $t$ 次字符串的研究，对于每组数据：
第一行有两个正整数 $n,m$，分别表示字符串 $S,T$ 的长度。
第二行是字符串 $S$。
第三行是字符串 $T$。
输出格式
输入输出样例
输入样例 #1
3
6 2
10-01-
01
7 3
010-1-1
101
6 4
111-00
1100输出样例 #1
2
1
2输入样例 #2
见附件中的 string2.in输出样例 #2
见附件中的 string2.out说明
**【样例 1 解释】**
对于第一组数据，有以下两种方案：
– 第一个 `-` 删 $R$ 的开头，第二个 `-` 删 $R$ 的结尾。
– 第一个 `-` 删 $R$ 的结尾，第二个 `-` 删 $R$ 的开头。
**【数据范围】**
对于 $20\%$ 的数据，$n,m\le 15$。
对于 $30\%$ 的数据，$n,m\le 30$。
对于 $70\%$ 的数据，$n,m\le 80$。
对于另 $10\%$ 的数据，保证答案不超过 $1$。
对于 $100\%$ 的数据，$1\le t\le 5$，$1\le n,m\le 400$。
解题思路
30分：暴力枚举遇到-的时候，是删除开头还是结尾，最后验证字符串是否一样。
70分：记忆化，记录处理到第k个字符，当前字符串是什么，后面匹配成功的方案数。
100分：当前字符串种类很多，无法全部记忆化，考虑他跟字符串t的关系。
对于新加入的字符，如果他跟字符串t能从头开始匹配，那么可以选择留着它（永不删除），或者选择删除它，可以从左边删除或者右边删除。如果从左边删除，那么当前的所有字符都必须从左边删除，不能存在永不删除和右边删除；如果是右边删除，不入队即可，记录右边删除次数。如果是永不删除，那么它跟之前永不删除的字符串接在一起，必须是t的前缀，且不能存在右边删除，因为它是新的右端。（感谢qzm123提供思路）
对于-号，要么删除左边，要么删除右边，前提是之前积累了删除的字符。
程序实现
dfs参数解释：k表示执行到第k个字符 、第k个操作；c表示有c个字符是永不删除的，他们跟字符串t的前缀可以匹配成功；x表示前k个字符中，有x个01在左边被删除；y表示有y个01在右边被删除。
原来是这样用的 😉