K-pop Strings

Time limit7sMemory limit512 MB

Summary

Count strings of length n over 35 characters that contain no tandem repeat of length n-k or more, modulo 998244353.

Level: Hard8 of 10
Topics: String, Dynamic programming, String matching
Solved: No attempts yet

Problem

A substring $s[l..r]$ is a tandem repeat if $r - l + 1$ is even and $s[l...(l+r-1)/2] = s[(l+r+1)/2...r]$ .

Gennady built a method for counting the tandem repeats in a string with suffix structures. Now he has come up with a new type of string based on tandem repeats. Gennady calls a string $s$ of length $n$ a K-pop string if it has no tandem repeat of length $n - k$ or more. Count the K-pop strings of length $n$ that use only the characters "1", "2", ..., "9", "a", "b", ..., "z", modulo 998244353.

Input

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

Output

Output one integer: the number of K-pop strings of length $n$ for the given $k$ that use only nonzero digits and lowercase letters, modulo 998244353.

Hint

The answer for the first input is 35 because every string of length 1 is valid: "1", "2", ..., "9", "a", "b", ..., "z". The answer for the second input is $35^4 - 35^2$ .

Examples3

Example 1
Input
```
1 16
```
Expected output
```
35
```
Example 2
Input
```
4 0
```
Expected output
```
1499400
```
Example 3
Input
```
15 5
```
Expected output
```
911125634
```