| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 27 | 13 | 13 | 65.000% |
예로부터 돌은 훌륭한 대화의 수단이었다.
세종이는 건설적인 대화를 나누기 위해, $1$번부터 $N$번까지의 번호가 있는 $N$개의 가방에 적당한 개수의 돌을 담아두었다. 하지만 악마 경곽이는 대화를 방해하기 위해 다음과 같은 게임을 제안하였다. 아쉽게도 세종이는 경곽이가 제안한 게임을 거부할 수 없다.
악마 경곽이의 목표는 위의 게임을 통해서 적어도 하나의 가방에 들어있는 돌의 개수를 $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 5
5
2 2
3
School > GSHS x SASA > 제1회 GSHS x SASA 프로그래밍 경시대회 E번