AT_agc073_a.[AGC073A] Chords and Checkered

给定整数 $L, K$ 以及一个长度为 $N$ 的非负整数序列 $A = (A_1, A_2, \ldots, A_N)$。这里保证 $2K < L$ 且 $0 \leq A_1 < A_2 < \cdots < A_N < L$。

现有一个周长为 $L$ 的圆。在这个圆上的任意一点选为参考点，将沿圆周顺时针方向距离 $x$ 的点记作坐标为 $x$ 的点。对于每个 $i$（$1 \leq i \leq N$），考虑连接坐标为 $A_i$ 和 $A_i + K$ 的两点的弦，称该弦为第 $i$ 条弦。

对于一个弦集合 $s$，其得分按以下流程确定：

• 画出集合 $s$ 中所有的弦。这些弦将圆分割成若干个区域；用黑白两色对这些区域进行染色。首先，将包含圆心的区域染为白色，其余区域以相邻区域（被长度大于零的线段连接）的颜色不同原则交替染色。可以证明这种染色方式总是存在且唯一。得分即为被染成黑色的区域数。

总共有 $2^N$ 种取值的弦集合 $s$。请计算所有这些集合的得分之和，并对 $998244353$ 取模后输出。

输入通过标准输入给出，格式如下：

$L$ $K$ $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出答案。

样例解释 1

• 不选任何弦时，得分为 $0$。
• 只选第 $1$ 条弦时，得分为 $1$。
• 只选第 $2$ 条弦时，得分为 $1$。
• 选第 $1, 2$ 条弦时，得分为 $2$。

因此答案为 $4$，即这些情况的得分之和。

数据范围

• $1 \leq K$
• $2K < L \leq 10^9$
• $1 \leq N \leq 250000$
• $0 \leq A_1 < A_2 < \cdots < A_N < L$
• 所有输入均为整数。

由 ChatGPT 5 翻译