P16810 [Lanqiao Cup 2026 Python A] Light On/Off Reversal

In front of Xiao Lan, there are $n$ lamps in a row. Each lamp is initially either on or off. Therefore, there are $2^n$ different initial states in total. For a certain initial state, Xiao Lan will make $n + 1$ independent observations. Each observation starts directly from the same initial state (the observations do not affect each other): - Observation $0$: Do not change the state of any lamp, and record the number of lamps that are on in the whole row at this time. - Observation $k$ ($1 \le k \le n$): Based on the initial state, first flip the states of the first $k$ lamps (on becomes off, off becomes on), then record the number of lamps that are on in the whole row at this time. Let the numbers of lamps that are on obtained in these $n + 1$ observations be $b_0, b_1, \ldots, b_n$ in order. If, in the sequence $b_0, b_1, \ldots, b_n$, the number of distinct elements is exactly $m$, then this initial state is called good. Now, please help Xiao Lan compute how many good initial states there are in total. Since the answer may be very large, you only need to output the result modulo $998244353$.

Input one line containing two integers $n$ and $m$, separated by a single space.

Output one integer, representing the number of valid initial states modulo $998244353$.

### Sample Explanation When $n = 3, m = 2$, there are $2$ valid initial states that meet the requirement, namely “off, on, off” and “on, off, on”: If the initial state is “off, on, off”, then the sequence $b$ of numbers of lamps that are on after each observation is $[1, 2, 1, 2]$. The distinct elements are $1$ and $2$, so there are $2$ kinds. If the initial state is “on, off, on”, then the sequence $b$ is $[2, 1, 2, 1]$. The distinct elements are $2$ and $1$, so there are $2$ kinds. It can be verified that only these $2$ initial states satisfy the condition that the number of distinct elements is exactly $2$. ### Constraints For $30\%$ of the testdata, $1 \le n \le 20$. For $60\%$ of the testdata, $1 \le n \le 3000$, $1 \le m \le 45$. For all testdata, $1 \le n \le 2 \times 10^5$, $1 \le m \le 45$. Translated by ChatGPT 5