Little Sub 喜欢玩一个叫“Flip Me Please”的游戏。在这个游戏中，有 $n$ 盏灯，编号从 $1$ 到 $n$，分别连接到 $n$ 个开关上。灯的初始状态可能是开启或关闭，按下第 $i$ 个开关会改变第 $i$ 盏灯的状态（即：如果第 $i$ 盏灯是开启的，按下开关后它会关闭，反之亦然）。

游戏共包含 $k$ 轮，每一轮中，玩家必须恰好按下 $m$ 个不同的开关。游戏的目标是在游戏结束时将所有灯变为目标状态。

Little Sub 刚刚遇到了一个非常困难的挑战，他无法解决。作为他的朋友，你的任务是找出有多少种方案可以完成这个挑战，并输出答案对 $998244353$ 取模的结果。

如果存在两个整数 $i$ 和 $j$（$1 \le i \le k, 1 \le j \le n$），使得在第一种方案的第 $i$ 轮中按下了第 $j$ 个开关，而在第二种方案的第 $i$ 轮中没有按下第 $j$ 个开关（反之亦然），则我们认为这两种方案是不同的。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$（约 $1000$），表示测试数据组数。对于每组测试数据：

第一行包含三个整数 $n, k, m$（$1 \le n, k \le 100, 1 \le m \le n$）。

第二行包含一个长度为 $n$ 的字符串 $s$，仅由 '0' 和 '1' 组成，表示灯的初始状态。如果第 $i$ 个字符为 '1'，则第 $i$ 盏灯初始为开启状态；如果第 $i$ 个字符为 '0'，则第 $i$ 盏灯初始为关闭状态。

第三行包含一个长度为 $n$ 的字符串 $t$，仅由 '0' 和 '1' 组成，表示灯的目标状态。如果第 $i$ 个字符为 '1'，则第 $i$ 盏灯在游戏结束时必须为开启状态；如果第 $i$ 个字符为 '0'，则第 $i$ 盏灯在游戏结束时必须为关闭状态。

保证 $n > 20$ 的测试数据不超过 $100$ 组。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。

样例

样例输入 1

3
3 2 1
001
100
3 1 2
001
100
3 3 2
001
100

样例输出 1

2
1
7

说明

对于第一个样例，Little Sub 可以在第 $1$ 轮按下第 $1$ 个开关，在第 $2$ 轮按下第 $3$ 个开关；或者在第 $1$ 轮按下第 $3$ 个开关，在第 $2$ 轮按下第 $1$ 个开关。因此答案为 $2$。

对于第二个样例，Little Sub 只能在唯一的一轮中按下第 $1$ 个和第 $3$ 个开关。因此答案为 $1$。