Problem Description

The smart Cirno started learning calculations, so she happily computed the sum from $1$ up to $n$.

She obtained an $n$-term sequence: $\{ a_n = 1 + 2 + 3 + 4 + ... + n \}$.

To check whether her calculation is wrong, she needs to pick two elements $v_1, v_2$ from the sequence according to some rule (the two elements may be the same), and then uniformly choose integers $a \in [ 1, v_1 ]$ and $b \in [ 1, v_2 ]$ to compare which one is larger.

So, she needs you to compute the probability that $a > b$.

The rule: The probability of selecting the $i$-th element of the sequence is:

$$\frac{a_i}{\sum\limits_{j=1}^n a_j}=\frac{3i\times(i+1)}{n(n+1)(n+2)}$$

Input Format

Input a positive integer $n$.

Output Format

Output the probability modulo $998244353$.

2

686292993

Hint

For the first $5\%$ of the testdata, $n = 3$.

For the first $15\%$ of the testdata, $n \le 100$.

For the first $30\%$ of the testdata, $n \le 5000$.

For the first $55\%$ of the testdata, $n \le 10^7$.

For the first $95\%$ of the testdata, $1 \le n \le 10^{18}$, and neither $n$ nor $n+2$ is a multiple of $998244353$.

For the last $5\%$ of the testdata, $n = 0$ means $n$ is positive infinity.

Translated by ChatGPT 5