P14043 [SDCPC 2019] Flipping Game

小 Sub 喜欢玩游戏 $\textit{Flip Me Please}$。在这款游戏中，有 $n$ 盏灯，编号从 $1$ 到 $n$，分别连接着 $n$ 个开关。这些灯起初可能是亮着也可能是灭着的，按下第 $i$ 个开关会将第 $i$ 盏灯的状态切换为相反状态（也就是说，如果第 $i$ 盏灯是亮的，按下开关后变为灭的；若本来是灭的，按下后变为亮的）。 游戏一共进行恰好 $k$ 轮，每一轮玩家必须按下恰好 $m$ 个不同的开关。游戏的目标是在结束时让所有的灯达到目标状态。 小 Sub 正在遇到一道很难的挑战，他实在解不出来。作为他的朋友，你的任务是帮他计算有多少种不同的按开关方法可以达成目标，并将结果对 $998244353$ 取模后告诉他。 当且仅当存在整数 $i,j$，$1 \le i \le k$，$1 \le j \le n$，使得在第一种方法的第 $i$ 轮按了第 $j$ 个开关而第二种没有，或者反之，则认为两种按法不同。

有多组测试数据。输入的第一行为一个整数 $T$（约为 $1000$），表示测试用例的组数。对于每组测试数据： 第一行包含三个整数 $n$，$k$，$m$（$1 \leq n, k \leq 100$，$1 \leq m \leq n$）。 第二行是一个由 $0$ 和 $1$ 组成的长度为 $n$ 的字符串 $s$，表示灯的初始状态。若第 $i$ 个字符是 `1`，则第 $i$ 盏灯初始为亮，否则为灭。 第三行是一个由 $0$ 和 $1$ 组成的长度为 $n$ 的字符串 $t$，表示灯的目标状态。若第 $i$ 个字符是 `1`，则第 $i$ 盏灯最终应为亮，否则应为灭。 保证 $n > 20$ 的测试数据不会超过 $100$ 组。

对于每组测试数据输出一行一个整数，表示满足条件的方案数。

对于第一组示例测试，小 Sub 可以在第 $1$ 轮按下第 $1$ 个开关，在第 $2$ 轮按下第 $3$ 个开关；或第 $1$ 轮按下第 $3$ 个开关，第 $2$ 轮按下第 $1$ 个开关。所以答案是 $2$。 对于第二组示例测试，小 Sub 只能在唯一一轮按下第 $1$ 个和第 $3$ 个开关。所以答案是 $1$。 由 ChatGPT 5 翻译