配点 : 1000 点
問題文
1 我决定将所有值添加到 N 的顺序编号 N 方块排成一条直线。其中 B_1, ..., B_K 的 K 广场内有障碍物,无法进入。
高桥君从现在开始要做弥撒。 启动 1 并 我即将前往 N 。
不过,高桥可以使用的移动方式是有限制的。1 第二步,高桥 当你在 x 您只能移动到 x + D_1, x + D_2, ..., x + D_M 中的一个方格。
有障碍物的方块, 您只能跳转到N 方格。
高桥君 1 移动到广场 x 来自质量 当移动到 y 时,满足以下条件的最小非负整数: 它的成本是 i 。
- x + 1 以上 y 以下任意整数 不能被 2^i 整除。
重复从一个方格移动到另一个方格 来自 1 到 N 的路径的成本是每次行程的成本之和。
所有可能路线的成本总和为 除以 998244353 后求余数。
制約
- 3 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N-2
- 1 \leq M \leq N-1
- 1 < B_1 < B_2 < \cdots < B_K < N
- 0 < D_1 < D_2 < \cdots < D_M < N
- 所有输入均为整数 打印除以
入力
输入将以以下形式从标准输入给出。
N K M B_1 B_2 \cdots B_K D_1 D_2 \cdots D_M
出力
所有可能路线的成本总和为 除以 998244353 后的余数。
入力例 1
3 1 2 2 1 2
出力例 1
2
可能的路线是 仅那些移至 1 到 3 的。
满足条件的最小非负整数为 2 可以验证如下,所以质量 移动到 1 到 3 的成本是 2 。
- 2^1 = 2 中 由于 2 可整除,1 不满足条件。
- 2^2 = 4 中 由于 2, 3 都不可整除,所以2 满足条件。
因此,该路线的成本为 2 。
入力例 2
4 1 3 3 1 2 3
出力例 2
8
可能的路线如下 2 有一条街。 转至
-
质量 重复从 1 到 4 。这条路线的费用是 转到 3 。
-
质量 重复从 1 到 2 并 2 到 4 。这条路线的费用是 转到 2 + 3 = 5 。
因此,所有路由的成本总和为 8 。
入力例 3
4 2 2 2 3 1 2
出力例 3
0
首先质量 我无法到达 4 ,所以0 。
入力例 4
10 2 4 2 7 1 2 3 9
出力例 4
301