P7145 [THUPC 2021 Preliminary] Legal Sequence

For a $0$-$1$ sequence $s$ of length $n$, we number its bits from left to right starting from $0$, denoted as $s_0, s_1, \ldots, s_{n-1}$. Given a positive integer $k$, take a subsegment of $s$ with length $k$. Interpret this subsegment as a $k$-bit binary number with the left side as the most significant bit and the right side as the least significant bit, denoted as $t$. Then $0 \le t < 2^k$. There are $n - k + 1$ subsegments of length $k$ in $s$. If for every such subsegment, after interpreting it as the binary number $t$ as above, the bit of $s$ with index $t$ (that is, $s_t$) is $1$, then $s$ is called legal. It is guaranteed that $2^k \le n$, so $t$ will not go out of range as an index of $s$. Given $n, k$, find the number of legal sequences $s$. Since the number of solutions may be large, you only need to output the result modulo $998, 244, 353$.

The input contains one line with two positive integers $n, k$ separated by a space. It is guaranteed that $1 \le k \le 4$, $2^k \le n \le 500$.

Output one line containing one non-negative integer, which is the number of legal solutions modulo $998, 244, 353$.

**Sample Explanation #1** There are two sequences that satisfy the requirement: $0, 1, 1, 1$ and $1, 1, 1, 1$. **Source** From the preliminary round of the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021). Resources such as the editorial can be found at . Translated by ChatGPT 5