Problem Description

Given a random permutation of length $n$, find the expected length of its longest increasing subsequence.

To avoid precision errors, you only need to output the remainder of the answer modulo $998244353$.

Input Format

The input consists of a single positive integer $n$.

Output Format

The output consists of a single non-negative integer, which is the remainder of the answer modulo $998244353$.

It can be proven that the answer is always a rational number, denoted as $a/b$ (where $a$ and $b$ are coprime integers). Let $x$ be the integer you output, then you need to ensure that $0 \le x < 998244353$ and $a$ is congruent to $b \cdot x$ modulo $998244353$.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1

Sample Input #2

2

Sample Output #2

499122178

Sample Input #3

3

Sample Output #3

2

Notes

[Sample #2 Explanation]

This corresponds to $3/2$.

[Data Range and Constraints]

For $100\%$ of the data, $1 \le n \le 28$.

There are 25 sets of data. For the $i$-th set of data ($1 \le i \le 25$), $n = i + 3$.

见题面 Input 部分

见题面 Output 部分