Double Spanning Tree Sum

Given a positive integer n, consider the following process:

• Initially, an undirected, labeled, unrooted tree T on n vertices is chosen. All edges in T are colored white.
• Then, arbitrarily many additional undirected edges (colored black) are added subject to the condition that when the colors are ignored the resulting graph is a simple graph. (Hence, the newly‐added black edges can only be chosen from those pairs of vertices not already connected by a white edge.)
• Let S be the set of all graphs that can be obtained by this process.

For any connected graph G (recall that every graph produced in this process is connected since it contains a spanning tree), define f(G) to be the number of ways G can be produced; that is, the number of pairs (T, E) where T is a spanning tree of G (whose edges are white) and E is a subset (possibly empty) of the remaining edges (colored black) so that when combined the resulting graph (ignoring colors) is G. Equivalently, f(G) is the number of spanning trees in G.

It is known that

[ \sum_{G} f(G) = n^{n-2} \cdot 2^{\binom{n-1}{2}}, ]

where the summation is over all connected graphs G obtained via the above procedure.

Your task is to compute

[ \sum_{G} f(G)^2 \quad (\bmod; 998244353). ]

Note: Unfortunately, due to some restrictions the modulus 1004535809 cannot be used in place of 998244353.

Hint: One way to interpret the sum is to observe that every connected graph produced in the process has f(G) equal to its number of spanning trees. Thus, the sum in question may be rewritten as a sum over pairs of spanning trees. After some combinatorial manipulations (using for instance the Matrix–Tree Theorem), it can be shown that the answer is given by

[ n^{n-2} \cdot (n-1)^{n-2} \cdot 2^{\frac{(n-1)(n-2)}{2}} \quad (\bmod; 998244353). ]

Compute and output the above quantity.

inputFormat

The input consists of a single line containing one positive integer n (2 ≤ n).

outputFormat

Output a single integer – the value of

[ n^{n-2} \cdot (n-1)^{n-2} \cdot 2^{\frac{(n-1)(n-2)}{2}} \quad (\bmod; 998244353). ]

sample

2

1