고전적인 합 문제

공화국 Never에는 도시 $n$개와 도로 $n-1$개가 있다. 도시에는 1번부터 $n$번까지 번호가 붙어 있다. 도로에는 1번부터 $n-1$번까지 번호가 붙어 있으며, $i$번 도로는 도시 $i$와 도시 $i + 1$을 잇는다. 모든 도로는 양방향으로 통행할 수 있다. 거리 $d(u, v) = |u - v|$는 도시 $u$에서 도시 $v$로 이동하는 데 지나야 하는 도로 수의 최솟값이다.

$k$명의 친구가 만나려고 한다. $i$번째 친구는 도시 $a_i$에 산다. 친구들은 $\sum_{i=1}^k d(v, a_i)$를 최소로 만드는 도시 $v$를 고른다. 그런 도시가 여러 개이면 그중 번호가 가장 작은 도시를 고른다.

친구 수만 알고 친구들이 사는 도시는 모른다. 각 친구는 $n$개 도시 중 어디에나 살 수 있으므로 가능한 경우는 모두 $n^k$가지이다. 모든 경우에 대해 친구들이 고른 도시 번호를 모두 더한 합을 구하라.

첫 줄에 도시 수 $n$과 친구 수 $k$가 주어진다 ($2 \le n, k \le 10^6$).

$n^k$가지 경우의 합을 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 번째 경우는 도시가 3개, 친구가 2명이므로 가능한 경우가 $3^2 = 9$가지이다. 친구 중 한 명이라도 도시 1에 살면 친구들은 도시 1을 고르며, 이런 경우는 5가지이다. 그렇지 않고 친구 중 한 명이라도 도시 2에 살면 도시 2를 고르며, 이런 경우는 3가지이다. 나머지 1가지는 두 친구가 모두 도시 3에 사는 경우이며, 이때 도시 3을 고른다. 따라서 합은 $5 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 14$이다.