재우의 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$이지만, 이 문제에서는 고려하지 않도록 하자.