子串计数

给出两个字符串 $s_1$ 和 $s_2$ ，在 $i > 2$ 时 有 $s_i=s_{i-2}+s_{i-1}$ ，其中 $+$ 表示将字符串首尾相连，求 $s_n$中有多少个子串是 "111" 。

假设 $s_1="01"$,$s_2="1"$，则 $s_3="011"$,$s_4="1011"$,$s_5="0111011"$ 。

字符串 $S$ 的子串定义为：删去 $S$ 前缀与后缀若干字符后得到的新字符串。

第一行一个整数 $T(1 \leq T \leq 50)$ ，表示测试数据组数，接下来包含 $T$ 组测试数据。

对于每组测试数据，第一行输入三个整数 $n,a,b\ (1 \leq n,a,b \leq 10^5)$ ，其中 $a,b$ 表示 $s_1$ 和 $s_2$ 的长度。

接下来输入一个长为 $a$ 的 $01$ 串 $s_1$。

最后一行输入一个长为 $b$ 的 $01$ 串 $s_2$。

对于每组测试数据，输出一个整数代表第 $n$ 个 $01$ 串中有多少个子串为 "111"。

由于答案很大，请你输出答案除以 $998244353$ 的余数。

3
5 2 1
01
1
10 1 1
0
0
5 1 1
1
1

1
0
3

内蒙古自治区第十五届大学生程序设计竞赛