P8559 Treasure

Ling is going treasure hunting on a grid of size $2$ rows and $n+1$ columns. With such a chance, she will not miss any treasure she can possibly get. Each cell has one of two states: **empty** or **wall**. **Empty** cells can be passed through freely. Also, except for the bottom cell of the first column, every empty cell contains a treasure. The first column is guaranteed to be empty, and it is also the entrance of the map. **Walls** cannot be passed through. Note that each move can only go to an adjacent cell, and the boundary of the map cannot be crossed either. Ling still does not know the exact layout of the map. While she is thinking about a strategy, Mio says: “I know the map has exactly $k$ walls. Among all possible maps, in how many cases can you find exactly $m$ treasures?” “So what if I don’t answer?” Ling only wants to dig for treasure, and replies lightly. “Huh? Then I won’t tell you about several treasure locations~” Mio looks serious. “But I won’t make it too hard for you. You only need to output the answer modulo $998244353$.” With no choice, Ling asks you to help compute the answer.

A single line with three positive integers $n, k, m$.

A single line with one integer, the answer modulo $998244353$.

[Explanation for Sample 1] The map size is $2\times(3+1)$, with $3$ obstacles. There are $4$ cases where you can find exactly $2$ treasures, as shown below:  In the figure, the green part is the entrance, gray cells are walls, and white cells are **empty cells with treasure**. You can see that there are exactly $4$ cases where, starting from the entrance, you can reach exactly $2$ empty cells (and thus obtain $2$ treasures). So the answer is $4$. [Constraints] **This problem uses bundled testdata.** Subtask 1 (11 pts): $n\leq 12$. Subtask 2 (19 pts): $n\leq 1000$. Subtask 3 (31 pts): $n \leq 5\times 10^4$. Subtask 4 (39 pts): no additional constraints. For $100\%$ of the testdata, $2\le n \le 3\times 10^6$, $m, k\geq 2$, and $m+k\leq 2n$. [Note] This is an OI problem, not a proof problem. Translated by ChatGPT 5