28212번 - Classical Summation Problem 다국어

문제

There are $n$ cities and $n-1$ roads in the Republic of Never. The cities are conveniently 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 defined as the smallest number of roads one needs to use to move from city $u$ to city $v$.

There are $k$ friends who are looking to meet. The $i$-th friend lives in city $a_i$. For the meeting, the friends will choose city $v$ such that $\sum \limits_{i=1}^k d(v, a_i)$ is minimum. If there are several such cities, they will choose the one with the smallest number among them.

Unfortunately, you know just the number of friends but nothing about the cities where they live. Every friend might live in any of the $n$ cities; hence, there are $n^k$ options overall. You would like to find the sum of the numbers of cities the friends will choose in all the $n^k$ options. Output this sum modulo 998ドル,244円,353円$.

입력

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

출력

Print the sum of the numbers of cities the friends will choose in all the $n^k$ options, modulo 998ドル,244円,353円$.

제한

노트

In the first example, with three cities and two friends, there are 3ドル^2 = 9$ options to consider. If either friend lives in city 1ドル,ドル the friends will choose city 1ドル,ドル and there are 5ドル$ such options. Otherwise, if either friend lives in city 2ドル,ドル the friends will choose city 2ドル,ドル and there are 3ドル$ such options. In the remaining case, if both friends live in city 3ドル,ドル they will choose city 3ドル,ドル and there is 1ドル$ such option. The total is 5ドル \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 14$.