Expected Spanning Tree Weight in Complete Graph

Given a complete graph with n vertices labeled from 1 to n, each edge connecting vertices i and j has a weight \( (i+j)^k \). A spanning tree is defined as a tree that covers all the vertices and has exactly \(n-1\) edges, and its weight is the sum of the weights of its edges. A spanning tree is chosen uniformly at random among all spanning trees of the complete graph.

It is known that in a complete graph, the probability that any fixed edge is present in a random spanning tree is \(\frac{2}{n}\). Hence, by linearity of expectation, the expected weight \(E\) of the spanning tree is

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

Since the answer can be large, output \(E\) modulo \(998244353\).

inputFormat

The only line of input contains two integers, n and k.

outputFormat

Output a single integer, which is the expected weight of the spanning tree modulo \(998244353\).

sample

3 1

8