27309번 - 재우의 F를 막아라

고려대학교에는 여러 운동 과목이 있다. 그중 일부 과목은 학교에 시설이 없는 관계로 외부 시설에서 진행한다. 재우가 수강 신청한 수영 과목 역시 마찬가지이다. 그러나 재우는 학기 초의 포부와는 달리 수영 수업을 가는 것을 매우 귀찮아 해 수영 수업을 한번도 가지 않았다. 시간이 흘러 종강 날이 다가와 수영 기말 평가를 진행하게 되었다.

수영장에는 길이가 $d$미터인 $N$개의 레인이 $1$번부터 $N$번까지 차례로 있고, 이웃한 두 레인 사이에는 벽이 한 개 씩 총 $N-1$개 있어 통과하지 못한다.

그러나 출발점과 끝점을 제외하고 $1$미터당 한 개씩 $d-1$개의 구멍이 $N-1$개의 벽 중 어느 하나에 존재해 해당 구멍을 통해 이웃한 레인으로 이동할 수 있다.

아래는 $d=6$, $N=4$의 예시이다. 이 경우 출발점과 끝점을 제외하고 $1$미터당 한 개씩 총 5개의 구멍이 존재한다.

수영 강사는 한 번도 출석하지 않은 학생이 있다는 사실을 알아차리고, 해당 학생을 F 학점을 주기 위한 방안으로 다음과 같은 <평가 조건>을 마지막 수업시간에 말해줬다.

<평가 조건>

$a$번 레인에서 출발하면, $a$번 레인으로 도착할 것

$a$는 $1$부터 $N$까지의 수 중 시험 당일 동일한 확률로 랜덤하게 하나가 정해짐

재우는 평가 조건을 들은 적이 없기 때문에 만나는 통로마다 이웃한 레인으로 이동하기로 했다. 수영장에 있는 $d-1$개의 통로는 각각 독립적으로 $N-1$개의 벽에 동일한 확률로 랜덤하게 존재한다고 가정할 때, 재우가 받을 학점의 기댓값을 구해보자.

단, 수영 과목은 1학점이며, <평가 조건>을 만족하면 Pass를 받아 1학점, 그렇지 않으면 Fail을 받아 0학점을 받는다. 또, 재우는 수영을 할 줄 알기 때문에, 재우의 방법에 맞게 도착할 수 있다.

아래는 위에서 설명한 그림의 예시이다. $a$가 $1$이나 $4$로 결정되면, 재우가 $1$번이나 $4$번 레인에서 출발해 화살표를 따라 출발한 레인과 다른 레인에 도착하여 <평가 조건>을 만족하지 않아 $0$학점을 받는다. $a$가 $2$나 $3$으로 결정되면 재우가 $2$번이나 $3$번 레인에서 출발해 출발한 레인과 같은 레인에 도착하여 <평가 조건>을 만족해 1학점을 받는다.

$d=6$, $N=4$일 때 수영장 레인이 아래와 같이 결정될 확률은 ${1\over{3^5}}$이며, 수영장 레인이 아래와 같이 결정된 후 재우의 학점의 기댓값은 $2\over4$이다.

첫 번째 줄에 레인의 개수를 나타내는 정수 $N$ ($2 \le N \le 20\,000$)과 수영장의 길이를 나타내는 정수 $d$ ($1 \le d \le 5\,000$)가 공백으로 구분되어 주어진다.

재우가 수영 과목에서 받을 학점의 기댓값을 $p$라고 할 때, $p\times (N^2-N)^{d-1}$를 $998\,244\,353$으로 나눈 나머지를 출력한다.

$p\times (N^2-N)^{d-1}$가 항상 정수임을 증명할 수 있다.

실제로 재우가 받은 학점은 $0$이지만 이 문제에서는 고려하지 않도록 하자.