P4484 [BJWC2018] Longest Increasing Subsequence

Given a uniformly random permutation of length $n$, compute the expected length of its longest increasing subsequence. To avoid precision errors, you only need to output the answer modulo $998244353$.

The input contains a single positive integer $n$.

Output a single non-negative integer, the remainder of the answer modulo $998244353$. It can be proved that the answer is a rational number; let it be $a/b$ ($a, b$ are coprime integers). Let the integer you output be $x$. You must ensure $0 \le x < 998244353$ and $a \equiv b x \pmod{998244353}$.

Sample #2 Explanation: This is $3/2$. Constraints: - For $100\%$ of the data, $1 \le n \le 28$. - There are 25 testcases. For the $i$-th testcase ($1 \le i \le 25$), $n = i + 3$. Translated by ChatGPT 5