斐波那契自动机

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

某个字符串的子串指的是原字符串中连续的一段，例如“abc”的子串可以是“a”，“b”，“c”，“ab”，“bc”，“abc”。01串“100111”中有2个子串是“11”。

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

第一行一个整数 $T(1 \leq T \leq 100)$ ，表示测试数据组数，接下来包含 $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$ 串中有多少个子串是 “11”。

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

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

3
0
4

杭州电子科技大学2020新生编程大赛