给你两个巨大的二进制整数 $$$a$$$ 和 $$$b$$$,长度分别为 $$$n$$$ 和 $$$m$$$。您将重复以下过程:如果 $$$b > 0$$$,则将值 $$$a~ \&~ b$$$ 添加到答案中,并将 $$$b$$$ 除以 $$$2$$$ 向下舍入(即删除 $$$b$$$ 的最后一位数字),然后再次重复该过程,否则停止该过程。
值 $$$a~ \&~ b$$$ 表示 $$$a$$$ 和 $$$b$$$ 的按位与。您的任务是计算以 $$$998244353$$$ 为模的答案。
请注意,您应该以十进制形式(而不是二进制形式)将值 $$$a~ \&~ b$$$ 添加到答案中。所以你的任务就是用十进制计算答案。例如,如果 $$$a = 1010_2~ (10_{10})$$$ 且 $$$b = 1000_2~ (8_{10})$$$,则值 $$$a~ \&~ b$$$ 将等于 $$$8$$$,而不是 $$$1000$$$。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是 $$$a$$$ 的长度和 $$$b$$$ 的长度。
输入的第二行包含一个巨大的整数$$$a$$$。保证这个数字恰好由 $$$n$$$ 个零和一个组成,并且第一个数字始终是 $$$1$$$。
输入的第三行包含一个大整数$$$b$$$。保证该数字恰好由 $$$m$$$ 个零和一个组成,并且第一位数字始终为 $$$1$$$。
输出
以十进制表示法模 $$$998244353$$$ 打印此问题的答案。
示例
输入 #1
4 4 1010 1101
输出 #1
12
输入 #2
4 5 1001 10101
输出 #2
11
注意
第一个示例的算法:
1. 添加答案 $$$1010_2~ \&~ 1101_2 = 1000_2 = 8_{10}$$$ 并设置 $$$b := 110$$$;
2. 添加答案 $$$1010_2~ \&~ 110_2 = 10_2 = 2_{10}$$$ 并设置 $$$b := 11$$$;
3. 添加答案 $$$1010_2~ \&~ 11_2 = 10_2 = 2_{10}$$$ 并设置 $$$b := 1$$$;
4. 添加答案 $$$1010_2~ \&~ 1_2 = 0_2 = 0_{10}$$$ 并设置 $$$b := 0$$$。
所以答案是 $$$8 + 2 + 2 + 0 = 12$$$。
第二个例子的算法:
1. 添加答案 $$$1001_2~ \&~ 10101_2 = 1_2 = 1_{10}$$$ 并设置 $$$b := 1010$$$;
2. 添加答案 $$$1001_2~ \&~ 1010_2 = 1000_2 = 8_{10}$$$ 并设置 $$$b := 101$$$;
3. 添加答案 $$$1001_2~ \&~ 101_2 = 1_2 = 1_{10}$$$ 并设置 $$$b := 10$$$;
4. 添加答案 $$$1001_2~ \&~ 10_2 = 0_2 = 0_{10}$$$ 并设置 $$$b := 1$$$;
5. 添加答案 $$$1001_2~ \&~ 1_2 = 1_2 = 1_{10}$$$ 并设置 $$$b := 0$$$。
所以答案是 $$$1 + 8 + 1 + 0 + 1 = 11$$$。