문자열 제작

시간 제한1초메모리 제한1024 MB

요약

길이 N인 대문자 문자열 두 개 가운데, 'A'로만 이루어진 가장 긴 공통 부분수열의 길이가 정확히 M인 쌍의 개수를 998244353으로 나눈 나머지를 구한다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

알파벳 대문자를 이용하여 길이 $N$ 인 두 문자열 $S\_1$ 과 $S\_2$ 를 만들려고 한다.

어떤 문자열 $S$ 에서 $0$ 개 이상의 문자를 지워서 만든 새로운 문자열을 $S$ 의 부분수열이라고 한다. $S\_1$ 과 $S\_2$ 의 공통 부분수열이면서 A로만 이루어진 문자열을 공통 A-부분수열이라고 부를 때, 가장 긴 공통 A-부분수열의 길이가 $M$ 인 경우의 수를 구해 보자.

입력

첫 번째 줄에 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 정답을 $998 \\, 244 \\, 353$ 으로 나눈 나머지를 출력한다.

제한

$1 \le M \le N \le 2 \times 10^5$

예제2

예제 1
입력
```
2 1
```
예상 출력
```
2600
```
예제 2
입력
```
2023 12
```
예상 출력
```
139579432
```