Polynomial Interpolation of the Reciprocal Function

In an electrical experiment, the voltage across a resistor box is maintained constant at \(1\,V\). The resistance is adjusted sequentially to \(1\,\Omega, 2\,\Omega, \ldots, n\,\Omega\) and the corresponding currents measured are \(1\,A, \frac{1}{2}\,A, \ldots, \frac{1}{n}\,A\) respectively (where the values are interpreted modulo \(998244353\)).

When describing the experimental conclusions, two students disagree:

• Student K: It is well known that if the voltage across a resistor is fixed, the current is inversely proportional to the resistance; that is, for a resistor of \(x\,\Omega\), the current is \(\frac{1}{x}\,A\).
• Student L: But why not use a polynomial of degree at most \(n-1\) to fit the \(n\) data points?

To prove Student L wrong, Student K challenges him to compute the value of the \(n-1\) degree polynomial (that exactly fits the \(n\) points \(P(k)=\frac{1}{k}\) for \(k=1,2,\ldots,n\)) evaluated at \(x = n+1\), under the arithmetic modulo \(998244353\). Note that the experimental data and results are all taken modulo \(998244353\) for convenience.

Important: When \(n\) is too large such that any value in the experiment (or the final result) becomes meaningless (specifically, if \(n \ge 998244353\) or \(n+1 \equiv 0 \;({\rm mod}\;998244353)\)), output \(-1\).

Hint: Define \(P(x)\) to be the \(n-1\) degree polynomial satisfying \(P(k)=\frac{1}{k}\) for \(k=1,2,\ldots,n\). Consider the polynomial \(Q(x)=xP(x)-1\) which vanishes at \(x=1,2,\ldots,n\). Thus, \(Q(x)=c(x-1)(x-2)\cdots(x-n)\). Determine \(c\) by evaluating at \(x=0\) and then compute \(P(n+1)\).

The final result is given by:

• If \(n\) is even, \(P(n+1)=0\).
• If \(n\) is odd, \(P(n+1)=\frac{2}{n+1}\) (modulo \(998244353\)).

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^{9}\) typically, but note the special conditions given below). All arithmetic should be performed modulo \(998244353\).

Note: If \(n \ge 998244353\) or \(n+1 \equiv 0 \;({\rm mod}\;998244353)\), the output should be \(-1\).

outputFormat

Output a single integer representing \(P(n+1)\) modulo \(998244353\) or \(-1\) if the data is meaningless as described.

sample

1

1