A - Chords and Checkered 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

整数 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 に含まれる弦をすべて描く．描いた弦によって円がいくつかの領域に分かれるので，それらを白と黒で塗る． まず円の中心が含まれる領域を白く塗り，残りの領域は，(長さ正の線分で)隣接する領域の色が異なるように塗る． このような塗り方は常に一意に存在することが証明できる． ここで黒く塗られた領域の個数をスコアとする．

s としてあり得る集合は 2^N 通りあります． これらすべてに対するスコアの総和を 998244353 で割ったあまりを求めてください．

制約

  • 1 \leq K
  • 2K < L \leq 10^9
  • 1 \leq N \leq 250000
  • 0 \leq A_1 < A_2 < \cdots < A_N < L
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

L K N
A_1 A_2 \ldots A_N

出力

答えを出力せよ．

入力例 1

5 2 2
0 1

出力例 1

4
  • 弦を 1 つも選ばない場合，スコアは 0 です．
  • 弦 1 を選ぶ場合，スコアは 1 です．
  • 弦 2 を選ぶ場合，スコアは 1 です．
  • 弦 1,2 を選ぶ場合，スコアは 2 です．

よって，これらの合計である 4 が答えです．

入力例 2

3 1 1
2

出力例 2

1

入力例 3

5 2 5
0 1 2 3 4

出力例 3

80

入力例 4

7 3 3
0 2 3

出力例 4

12

Score : 700 points

Problem Statement

You are given integers L, K and a length-N non-negative integer sequence A = (A_1, A_2, \ldots, A_N). Here, 2K < L and 0 \leq A_1 < A_2 < \cdots < A_N < L are guaranteed.

Consider a circle with circumference L. Take an arbitrary point on this circle as the reference point, and call the point reached by traveling clockwise distance x along the circumference from there the point with coordinate x. Also, for each i (1 \leq i \leq N), consider the chord connecting the point with coordinate A_i and the point with coordinate A_i + K, and call this chord i.

For a set of chords s, the score is determined by the following procedure:

  • Draw all chords contained in s. The drawn chords divide the circle into several regions; color them with white and black. First, color the region containing the center of the circle white, and color the remaining regions so that adjacent regions (connected by a line segment of positive length) have different colors. It can be proved that such a coloring method always exists uniquely. The score is the number of regions colored black.

There are 2^N possible sets for s. Find the sum, modulo 998244353, of scores for all of these.

Constraints

  • 1 \leq K
  • 2K < L \leq 10^9
  • 1 \leq N \leq 250000
  • 0 \leq A_1 < A_2 < \cdots < A_N < L
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

L K N
A_1 A_2 \ldots A_N

Output

Output the answer.

Sample Input 1

5 2 2
0 1

Sample Output 1

4
  • When no chords are chosen, the score is 0.
  • When chord 1 is chosen, the score is 1.
  • When chord 2 is chosen, the score is 1.
  • When chords 1, 2 are chosen, the score is 2.

Therefore, the answer is 4, which is the sum of these.

Sample Input 2

3 1 1
2

Sample Output 2

1

Sample Input 3

5 2 5
0 1 2 3 4

Sample Output 3

80

Sample Input 4

7 3 3
0 2 3

Sample Output 4

12