Four Vertex

問題文

$4$ 頂点のラベル付き完全グラフであって、各辺の重みが $1,2,\ldots,N$ のいずれかであるようなものは全部で $N^6$ 個ありますが、それらの最小全域木の重みの総和を $998244353$ で割った余りを求めてください。

制約

• $1\leq N \leq 200000$ 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

1

出力例1

3

全ての辺の重みが $1$ であるような $4$ 頂点の完全グラフの最小全域木の重みは $3$ です。 　
　

入力例2

2

出力例2

226

最小全域木の重みが $3$ となるものが $38$ 個、 $4$ となるものが $19$ 個、 $5$となるものが $6$ 個、 $6$ となるものが $1$ 個あります。
よって、重みの総和は $38×3+19×4+6×5+1×6=226$ です。　
　

入力例3

178096

出力例3

714149329

$998244353$ で割った余りを求めることを忘れずに。