#P18352. Witnessing the Miracle

Witnessing the Miracle

Witnessing the Miracle

数轴上放有若干磁铁,初始时它们的坐标是 [1,n][1,n] 内互不相同的整数。

每次操作必须恰好选择一块当前存在的磁铁,将它取走。随后:

  • 位于被取走磁铁左边的所有磁铁,坐标都减 11;
  • 位于被取走磁铁右边的所有磁铁,坐标都加 11。

称一次实验合法,当且仅当进行了恰好 kk 次操作,并且最终所有剩余磁铁的坐标都在 [1,n][1,n] 内。**操作过程中,磁铁坐标可以暂时超出 [1,n][1,n],甚至可以不是正数。**只要求最终状态满足范围限制。

用长度为 nn 的二进制串表示初始状态和最终状态:第 ii 位为 11,表示坐标 ii 上有磁铁;为 00,表示没有磁铁。

现在给定两个长度为 nn、仅含 0,1,?0,1,? 的字符串 S,TS,T。把两串中的每个问号分别替换为 00 或 11。求有多少种替换方案,使得存在一次合法实验,其初始状态恰好为填完后的 SS,最终状态恰好为填完后的 TT。

计数对象是填完后的字符串对 (S,T)(S,T)。同一个字符串对即使对应多种操作顺序,也只计一次。答案对 998 244 353998\,244\,353 取模。

输入格式

第一行一个整数 tt,表示测试用例数。

对于每个测试用例:

  • 第一行两个整数 n,kn,k;
  • 第二行字符串 SS;
  • 第三行字符串 TT。

数据范围:

  • 1≤t≤50001\le t\le5000;
  • 1≤n≤50001\le n\le5000;
  • 0≤k≤n0\le k\le n;
  • ∣S∣=∣T∣=n|S|=|T|=n,两串均只含字符 0,1,?0,1,?;
  • 一个输入文件中所有 nn 的和不超过 50005000。

输出格式

对于每个测试用例,输出一行一个整数,表示答案对 998 244 353998\,244\,353 取模的结果。

样例输入 1

3
7 3
1111111
1100011
10 3
??????????
??????????
5 2
??1?1
?0?1?

样例输出 1

1
3384
3