P5437 [XR-2] Promise

> "Xiaoyuan, don't go! After we part, when will we meet again?" > > "Xiaoyan, we will definitely see each other again! Before that, this is only a short farewell..."

Just because of that promise, Xiaoyan began a wait with no end in sight. In Xiaoyan's heart, the promise turned into a graph with $n$ vertices. At the beginning, it was a complete graph. The vertices are numbered from $1$ to $n$, and the weight of the edge connecting vertices $i, j$ is $(i+j)^k$. However, during the waiting, time was also slowly wearing away her faith, so some edges in the graph were randomly deleted. In the end, the graph became a tree with $n$ vertices, and stayed in Xiaoyan's heart forever. A very, very long time later, Xiaoyan's magic ran out, and she was on the verge of breaking down in pain and despair. Just then, Xiaoyuan finally came to find Xiaoyan. To save her only friend, she must know the result of the expected total edge weight of this tree modulo $998244353$. Can you help Xiaoyuan compute the answer, so she can fulfill that promise?

One line with two positive integers $n, k$.

One line with one integer, the value of the answer modulo $998244353$.

[Sample $1$ Explanation] This complete graph has $3$ nodes and $3$ edges, forming a cycle. The weights of these edges are: $3, 4, 5$. In the end, there are also $3$ possible trees, with total weights $7, 8, 9$. The expected value is $8$. [Constraints and Agreements] **This problem uses bundled testdata.** Subtask 1 (5 points): $1 \le n \le 5$, $1 \le k \le 10$. Subtask 2 (11 points): $k = 1$. Subtask 3 (11 points): $1 \le n, k \le 20000$. Subtask 4 (13 points): $1 \le n, k \le 10^5$. Subtask 5 (23 points): $1 \le k \le 10^5$. Subtask 6 (37 points): no special constraints. For $100\%$ of the data, $1 \le n \le 998244352$, $1 \le k \le 10^7$. **** > "Sorry to have kept you waiting... You have worked so hard until today..." > > "Xiaoyuan..." > > "Come, let's go. From now on, we will never be apart..." > > "Yes. I have been waiting for this moment—so long it felt like forever." Translated by ChatGPT 5