{"problem":{"name":"Chords and Checkered","description":{"content":"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 w","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc073_a"},"statements":[{"statement_type":"Markdown","content":"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.\nConsider 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$.\nFor a set of chords $s$, the **score** is determined by the following procedure:\n\n*   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.\n\nThere are $2^N$ possible sets for $s$. Find the sum, modulo $998244353$, of scores for all of these.\n\n## Constraints\n\n*   $1 \\leq K$\n*   $2K < L \\leq 10^9$\n*   $1 \\leq N \\leq 250000$\n*   $0 \\leq A_1 < A_2 < \\cdots < A_N < L$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$L$ $K$ $N$\n$A_1$ $A_2$ $\\ldots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc073_a","tags":[],"sample_group":[["5 2 2\n0 1","4\n\n*   When no chords are chosen, the score is $0$.\n*   When chord $1$ is chosen, the score is $1$.\n*   When chord $2$ is chosen, the score is $1$.\n*   When chords $1, 2$ are chosen, the score is $2$.\n\nTherefore, the answer is $4$, which is the sum of these."],["3 1 1\n2","1"],["5 2 5\n0 1 2 3 4","80"],["7 3 3\n0 2 3","12"]],"created_at":"2026-03-03 11:01:13"}}