Expected Hamiltonian Cycles in a Tournament

We call a tournament (a directed graph in which every pair of distinct vertices is connected by exactly one directed edge) recordable if it contains a directed Hamiltonian cycle (i.e. a cycle that visits every vertex exactly once and returns to the starting vertex). Consider all recordable tournaments on n vertices (vertices are labeled distinctly). One tournament is chosen uniformly at random among them. Your task is to compute the expected number of directed Hamiltonian cycles in the chosen tournament.

The answer is a rational number. More precisely, if the answer is \(\frac{q}{p}\) in reduced form then you are required to output an integer \(x\) with \(0 \le x < 998244353\) such that

[ px \equiv q \pmod{998244353}. ]

You may assume that such an \(x\) exists and is unique. If there is no recordable tournament, output -1.

Note: A tournament is recordable if and only if it is strongly connected. It is known that for \(n \ge 3\) the number of strongly connected tournaments on \(n\) vertices is \[ 2^{\binom{n}{2}} - n\,2^{\binom{n-1}{2}} \quad. \] For a tournament on n vertices, a simple counting shows that the total number of directed Hamiltonian cycles (if we consider two cycles different when their vertex sequences are different) in all tournaments is \[ (n-1)!\,2^{\binom{n}{2}-n}\,. \] A tournament that has a Hamiltonian cycle is necessarily strongly connected, so the expected number of Hamiltonian cycles in a recordable tournament is given by \[ E = \frac{(n-1)!\,2^{\binom{n}{2}-n}}{2^{\binom{n}{2}} - n\,2^{\binom{n-1}{2}}} = \frac{(n-1)!}{2\Bigl(2^{n-1} - n\Bigr)}\,. \]

Your task is to compute \(x\) where \(x \equiv \frac{(n-1)!}{2\Bigl(2^{n-1} - n\Bigr)} \pmod{998244353}\). If \(2^{n-1} - n = 0\) (i.e. if there is no recordable tournament), output -1.

inputFormat

The input consists of a single line containing one integer \(n\) (the number of vertices).

outputFormat

Output a single integer \(x\) satisfying the modular equation \(p x \equiv q \pmod{998244353}\) if a recordable tournament exists. Otherwise, output -1.

sample

1

-1