#P18352. Witnessing the Miracle
Witnessing the Miracle
Witnessing the Miracle
数轴上放有若干磁铁,初始时它们的坐标是 内互不相同的整数。
每次操作必须恰好选择一块当前存在的磁铁,将它取走。随后:
- 位于被取走磁铁左边的所有磁铁,坐标都减 ;
- 位于被取走磁铁右边的所有磁铁,坐标都加 。
称一次实验合法,当且仅当进行了恰好 次操作,并且最终所有剩余磁铁的坐标都在 内。**操作过程中,磁铁坐标可以暂时超出 ,甚至可以不是正数。**只要求最终状态满足范围限制。
用长度为 的二进制串表示初始状态和最终状态:第 位为 ,表示坐标 上有磁铁;为 ,表示没有磁铁。
现在给定两个长度为 、仅含 的字符串 。把两串中的每个问号分别替换为 或 。求有多少种替换方案,使得存在一次合法实验,其初始状态恰好为填完后的 ,最终状态恰好为填完后的 。
计数对象是填完后的字符串对 。同一个字符串对即使对应多种操作顺序,也只计一次。答案对 取模。
输入格式
第一行一个整数 ,表示测试用例数。
对于每个测试用例:
- 第一行两个整数 ;
- 第二行字符串 ;
- 第三行字符串 。
数据范围:
- ;
- ;
- ;
- ,两串均只含字符 ;
- 一个输入文件中所有 的和不超过 。
输出格式
对于每个测试用例,输出一行一个整数,表示答案对 取模的结果。
样例输入 1
3
7 3
1111111
1100011
10 3
??????????
??????????
5 2
??1?1
?0?1?
样例输出 1
1
3384
3