P5442 [XR-2] Appointment (Enhanced Version)

Original problem link: [P5437](https://www.luogu.org/problemnew/show/P5437). Actually, during the contest I wanted to include this enhanced version qwq. But the team members strongly disagreed, so I posted it after the contest.

There is a complete graph with $n$ vertices, numbered from $1$ to $n$. For the edge connecting vertices $i$ and $j$, its weight is $(i+j)^k$. Define the weight of a tree as the sum of the weights of all its edges. Randomly choose a spanning tree from all spanning trees of this graph, and find the expected value of its weight. You need to output the answer modulo $998244353$.

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

One line containing one integer, representing the answer modulo $998244353$.

### Constraints $1\le n \le 10^{10000}$ $1\le k \le 10^7$ Translated by ChatGPT 5