K-pop 문자열

부분 문자열 $s[l..r]$은 $r - l + 1$이 짝수이고 $s[l...(l+r-1)/2] = s[(l+r+1)/2...r]$을 만족하면 탠덤 반복(tandem repeat)이다.

Gennady는 접미사 구조를 이용해 문자열 안의 탠덤 반복 개수를 세는 방법을 고안했다. 이제 그는 탠덤 반복을 바탕으로 한 새로운 종류의 문자열을 만들었다. 길이가 $n$인 문자열 $s$는 길이가 $n - k$ 이상인 탠덤 반복이 없으면 K-pop 문자열이라고 한다. "1", "2", ..., "9", "a", "b", ..., "z" 문자만으로 이루어진 길이 $n$의 K-pop 문자열 개수를 998244353으로 나눈 나머지를 구하라.

첫 줄에 두 정수 $n$과 $k$가 주어진다. $n$은 문자열의 길이이고, $k$는 매개변수이다 ($1 \le n \le 100$, $0 \le k \le 16$).

주어진 $n$과 $k$에 대해, 0이 아닌 숫자와 영어 소문자로만 이루어진 길이 $n$의 K-pop 문자열 개수를 998244353으로 나눈 나머지를 정수 하나로 출력한다.

첫 번째 입력의 답은 35이다. 길이가 1인 문자열은 모두 가능하기 때문이다: "1", "2", ..., "9", "a", "b", ..., "z". 두 번째 입력의 답은 $35^4 - 35^2$이다.