Expected Value of a1 in a Modified Sequence

You are given a sequence of length n defined as \(a_1,a_2,\ldots,a_n\) with initial values \(a_i=i\) for \(1\le i\le n\). Then, you perform exactly \(n-1\) operations on this sequence. In the i-th operation (for \(1\le i\le n-1\)), you choose an integer \(j\) uniformly at random from the range \([1,n-i]\) and update the sequence by setting

[ a_j \leftarrow a_j + 2,a_{n-i+1}. ]

Your task is to compute the expected value of \(a_1\) after all operations, and output the answer modulo \(998244353\). It can be shown that the final answer is given by the closed form expression

[ E[a_1] \equiv \frac{n(n+1)(2n+1)}{6} \pmod{998244353}. ]

Note that division modulo \(998244353\) means you need to multiply by the modular inverse of \(6\) modulo \(998244353\).

inputFormat

The input consists of a single line containing one integer n (\(1 \le n \le 10^9\)) — the length of the sequence.

outputFormat

Output the expected value of \(a_1\) modulo \(998244353\), as described in the problem.

sample

1

1