Treasure Hunt on a 2×(n+1) Grid

Rin is about to embark on a treasure hunt on a grid with 2 rows and n+1 columns. The grid is filled with cells that are either empty or a wall. An empty cell may contain a treasure unless it is the bottom cell of the first column. Note that the entire first column is guaranteed to be empty and acts as the entry point.

Rin will collect every treasure that she can actually reach. Two cells are considered adjacent if they share a common side, and neither walls nor the boundaries of the grid can be passed through.

However, the exact layout of the grid is not known in advance. Mio tells Rin, "I know that there are exactly k walls in the grid." For every valid grid configuration (where walls are placed in exactly k out of the available 2n cells – note that the first column is fixed as empty), Rin may obtain some treasures. In particular, a treasure is placed in a cell if and only if it is the bottom cell of a column (except the first column) and that cell is empty, and it will only count if it is accessible from the entrance.

Your task is to compute the number of grid configurations (modulo $998244353$) that yield exactly m treasures reachable from the entrance.

The movement rules are as follows:

• Rin starts in the first column (both cells are available as entry points and are connected to each other).
• From a cell, she can move to any adjacent cell (up, down, left, right) provided that cell is not a wall and is within the grid.

Note: In a column (except the first), the two cells can be in one of four configurations:

• (empty, empty) — cost $0$ walls. If at least one cell is reachable from the previous column, then both become reachable due to vertical connectivity, and the bottom cell (if reachable) yields a treasure.
• (empty, wall) — cost $1$ wall, only the top cell may be reachable.
• (wall, empty) — cost $1$ wall, only the bottom cell may be reachable (and if reached, a treasure is collected).
• (wall, wall) — cost $2$ walls; no cell is reachable in that column.

The connectivity for column j (for j ≥ 2) is determined by whether the corresponding cells are adjacent horizontally to a reachable cell in column j-1. Moreover, if in a column both cells are empty and at least one is reachable, then vertical movement makes the other cell reachable as well.

You are given three integers: n (which defines the grid as having 2 rows and n+1 columns), k (the total number of walls placed in columns 2 to n+1), and m (the exact number of treasures that must be reachable). Output the number of valid grid configurations modulo $998244353$.

The problem can be solved with dynamic programming by processing the grid column‐by‐column and keeping track of the reachable state as well as the number of walls used and treasures collected. For each column (from 2 to n+1), we consider each possible configuration and update the connectivity accordingly.

Formulas:

• For the (empty, empty) configuration (denoted as $p=3$ with cost $0$): $$\text{if } init_{top} \text{ or } init_{bottom} \text{ is true, then } newState = 3, \quad treasure += 1.$$
• For (empty, wall) ($p=1$, cost $1$): $$newState = \begin{cases} 1, & \text{if } init_{top} \text{ is true} \\ 0, & \text{otherwise} \end{cases}.$$
• For (wall, empty) ($p=2$, cost $1$): $$newState = \begin{cases} 2, & \text{if } init_{bottom} \text{ is true} \\ 0, & \text{otherwise} \end{cases}, \quad treasure += \begin{cases} 1, & \text{if } newState = 2 \end{cases}.$$
• For (wall, wall) ($p=0$, cost $2$): $$newState = 0.$$

Here, init_top and init_bottom indicate whether the top or bottom cell is reachable from the previous column, respectively.

inputFormat

The input consists of a single line containing three integers n, k, and m separated by spaces:

• n: Determines the grid size (2 rows and n+1 columns).
• k: The exact total number of walls placed in the grid (only in columns 2 to n+1).
• m: The exact number of treasures (reachable in bottom cells of columns 2 to n+1) that Rin must collect.

It is guaranteed that the first column is always empty.

outputFormat

Output a single integer — the number of grid configurations that yield exactly m reachable treasures, taken modulo $998244353$.

sample

1 0 1

1

</p>