P5389 [Cnoi2019] Math Class

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 a positive integer $n$.

Output the probability modulo $998244353$.

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