Background

Original problem link: 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.

Problem Description

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$.

Input Format

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

Output Format

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

3 1

8

4 3

450

1926 817

984167516

998244353 1

998244352

Hint

Constraints

$1\le n \le 10^{10000}$
$1\le k \le 10^7$

Translated by ChatGPT 5