시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB27131365.000%

문제

예로부터 돌은 훌륭한 대화의 수단이었다.

세종이는 건설적인 대화를 나누기 위해, $1$번부터 $N$번까지의 번호가 있는 $N$개의 가방에 적당한 개수의 돌을 담아두었다. 하지만 악마 경곽이는 대화를 방해하기 위해 다음과 같은 게임을 제안하였다. 아쉽게도 세종이는 경곽이가 제안한 게임을 거부할 수 없다.

  1. 경곽이는 $N$ 이하의 음이 아닌 정수 $k$를 고른 뒤, 가방을 $[1, \, k]$와 $[k + 1, \, N]$의 두 구간으로 나눈다. 구간에 속한 가방이 없어도 된다.
  2. 세종이는 경곽이가 나눈 두 구간 중 하나를 선택하여, 선택한 구간의 모든 가방에는 돌을 $1$개씩 추가하고 선택하지 않은 구간의 모든 가방에는 돌을 $1$개씩 뺀다.
  3. 경곽이가 만족할 때까지 1-2 과정을 반복한다.

악마 경곽이의 목표는 위의 게임을 통해서 적어도 하나의 가방에 들어있는 돌의 개수를 $0$개로 만드는 것이다. 반대로, 세종이는 경곽이가 목표를 이루지 못하게 하고자 한다. 세종이와 경곽이는 진지하기 때문에 항상 최선의 선택을 하며, 경곽이는 초기 상태를 보고 목표를 달성할 수 있는지 즉시 판단할 수 있다. 만약 자신의 목표 달성이 불가능하면, 경곽이는 흥미를 잃고 곧바로 자리를 떠난다.

한편 세종이는 하나의 가방에 너무 많은 돌을 넣으면 너무 무겁기 때문에, 초기에 각각의 가방에는 최소 $1$개, 최대 $M$개의 돌을 넣고자 한다. 초기 가방에만 최대 $M$개의 돌이 들어가면 되며, 게임을 하는 과정에서는 각 가방에 들어있는 돌의 개수가 $M$개를 넘어가도 된다.

세종이는 자신의 가방에 조건을 만족하도록 적절히 돌을 넣어 경곽이가 자리를 떠나게 만들고 싶다. 세종이를 도와 초기에 각 가방에 넣을 서로 다른 돌의 배치 가짓수를 $998 \, 244 \, 353$으로 나눈 나머지를 구해 보자. $998 \, 244 \, 353$은 소수다.

입력

첫 번째 줄에 가방의 개수 $N$과 하나의 가방에 넣을 수 있는 돌의 최대 개수 $M$이 공백으로 구분되어 주어진다. ($1 \leq N, \, M \leq 1 \, 000 \, 000$)

출력

첫 번째 줄에 세종이가 가방에 돌을 넣을 수 있는 서로 다른 배치의 가짓수를 $998 \, 244 \, 353$으로 나눈 나머지를 출력하라.

예제 입력 1

1 5

예제 출력 1

5

예제 입력 2

2 2

예제 출력 2

3

출처

School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 E번