33953번 - PPC와 CPP 2

문제

1ドル$ 이상의 정수 $N$과 2ドル$ 이상의 정수 $K$가 주어진다. P또는 C로만 이루어진 길이가 $(K+1)N$인 문자열 $a_1, a_2, \cdots, a_{(K+1)N}$에 다음 연산을 원하는 만큼 반복해서 빈 문자열로 만들 수 있다면 그 문자열을 PPC 문자열이라고 부른다.

• 현재 문자열에서 연속된 $K+1$개의 문자를 고른다. 고른 문자들이 P...PC 또는 CP...P를 이룬다면, 그 고른 문자들을 삭제한다. 그 후, 남은 문자들을 순서를 바꾸지 않고 다시 이어 붙인다.

예를 들어 $K=2$일 때 CPPPCP는 PPC 문자열이다.

• 현재 문자열에서 3,4,5ドル$번째 문자를 고르면 PPC를 이룬다. 고른 문자들을 삭제한 후 문자열은 CPP가 된다.
• 현재 문자열에서 1,2,3ドル$번째 문자를 고르면 CPP를 이룬다. 고른 문자들을 삭제한 후 문자열은 빈 문자열이 된다.

$N$과 $K$가 주어질때, 길이가 $(K+1)N$인 PPC 문자열의 개수를 998244353ドル$으로 나눈 나머지를 계산하시오.

입력

첫 번째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다. (1ドル \leq N \leq 200 000, 2 \leq K \leq 40$)

출력

길이가 $(K+1)N$인 PPC 문자열의 개수를 998244353ドル$으로 나눈 나머지를 출력하시오.

제한

힌트