Classical Summation Problem

The Republic of Never has $n$ cities and $n-1$ roads. The cities are numbered from $1$ to $n$. The roads are numbered from $1$ to $n-1$, and road $i$ connects cities $i$ and $i + 1$. Every road can be traversed in both directions. The distance $d(u, v) = |u - v|$ is the smallest number of roads one needs to use to move from city $u$ to city $v$.

$k$ friends want to meet. The $i$-th friend lives in city $a_i$. The friends choose a city $v$ that minimizes $\sum_{i=1}^k d(v, a_i)$. If several cities achieve the minimum, they choose the one with the smallest number.

You know only the number of friends, not the cities where they live. Each friend can live in any of the $n$ cities, so there are $n^k$ possible cases. Find the sum of the numbers of the cities the friends choose over all $n^k$ cases.

The only line contains two integers $n$ and $k$, the number of cities and the number of friends ($2 \le n, k \le 10^6$).

Print the sum over all $n^k$ cases, modulo $998\,244\,353$.

In the first case, there are 3 cities and 2 friends, so there are $3^2 = 9$ cases. If either friend lives in city 1, the friends choose city 1, which happens in 5 cases. Otherwise, if either friend lives in city 2, they choose city 2, which happens in 3 cases. In the remaining case, both friends live in city 3, and they choose city 3. The total is $5 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 14$.