Promise in the Tree

In memory of a promise, Xiao Yan once saw her agreement transform into a graph of n vertices. Initially, it was a complete graph with vertices numbered from \(1\) to \(n\), and the weight of the edge connecting vertices \(i\) and \(j\) is given by \((i+j)^k\).

However, as time passed, some edges were randomly removed, and eventually, the graph became a tree of n vertices that would forever remain in her heart.

Long after, when Xiao Yan’s magic had been exhausted and she was on the brink of collapse, Xiao Yuan finally came to find her. In order to save her only friend, she must know the expected sum of the edge weights of this tree modulo \(998244353\).

Can you help Xiao Yuan compute the answer and fulfill that promise?

Note: The expectation is taken over all trees that could result from the random removal process (i.e. a uniformly random spanning tree of the complete graph). It is known that in a complete graph of n vertices every edge is present in a random spanning tree with probability \(\frac{2}{n}\). Thus, the expected total weight is

[ E = \frac{2}{n} \sum_{1 \le i < j \le n} (i+j)^k \quad \text{mod } 998244353. ]

inputFormat

The input consists of a single line containing two integers n and k:

• n (number of vertices)
• k (the exponent in the weight formula)

outputFormat

Output a single integer, which is the expected sum of the weights of the tree's edges modulo 998244353.

sample

3 1

8