406261: GYM102331 K K-pop Strings

A substring $$$s[l..r]$$$ is a tandem repeat if $$$r-l+1$$$ is even and $$$s[l \ldots \frac{l+r-1}{2}] = s[\frac{l+r+1}{2} \ldots r]$$$.

Recently Gennady came up with a method to calculate the number of tandem repeats in a string using suffix structures, and now he came up with a new type of strings based on tandem repeats. Gennady thinks that string $$$s$$$ of length $$$n$$$ is a K-pop string if there are no tandem repeats of length $$$\geq n - k$$$.

Help him find the number of K-pop strings consisting only of the characters '1', '2', ..., '9', 'a', 'b', ..., 'z', modulo $$$998\,244\,353$$$.

The first line of input contains two integers $$$n$$$ and $$$k$$$: the required length of string and the parameter ($$$1 \leq n \leq 100$$$, $$$0 \leq k \leq 16$$$).

Output one integer: the number of K-pop strings of length $$$n$$$ for the given $$$k$$$, consisting only of nonzero digits and lowercase alphabetic characters, modulo $$$998\,244\,353$$$.

1 16

35

4 0

1499400

15 5

911125634

The answer for the first example is $$$35$$$ because all strings of length $$$1$$$ are possible: "1", "2", ..., "9", "a", "b", ..., "z".

The answer for the second example is $$$35^4 - 35^2$$$.