Description

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$.

Input Format

The input contains a single positive integer $n$.

Output Format

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}$.

1

1

2

499122178

3

2

Hint

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