Problem Description

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$.

Input Format

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 Format

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

4 2

2

Hint

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 https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5