Problem 4D Yuezheng Ling and Random Tree

Time Limit: 2s
Memory Limit: 256MB

Background

Statement

Yuezheng Ling and Luo Tianyi are two friends who love studying algorithms.

Yuezheng Ling gives Luo Tianyi a tree with \(n\) nodes, rooted at \(1\). The tree is generated according to the following algorithm:

1. For each node \(i\) in the range \([2, n]\), select a random node \(j\) from the range \([1, i-1]\)
2. add an edge between node \(i\) and node \(j\)

Luo Tianyi is fascinated by the tree and wants to find out the expected value of the average depth of all the nodes in the generated tree, modulo 998244353. In other words, if \(D(i)\) denotes the depth of node \(i\), then the expected value of the average depth of all the nodes is \(E(\frac{\sum_{i=1}^n D(i)}n)\)

Note that the depth of the root is considered to be \(0\).

Input

The input consists of a single integer n, the number of nodes in the tree.

Output

Output a single line containing the expected value of the average depth of all the nodes in the tree, modulo 998244353.

We can prove that the expected value is always rational. Additionally, under the constraints of this problem, when that value is represented as \(\frac QP\) with two coprime integers \(P\) and \(Q\), there is a unique integer \(R\) such that \(R\times Q\equiv P\pmod {998244353}\) and \(0≤R<998244353\). Find this \(R\).

Sample Input 1

3

Sample Output 1

831870295

Explanation 1

The expected value is \(\frac{5}{6}\)。

Constrains

For 60% of the test cases， \(1 \le n \le 10\).

For all test cases， \(1 \le n \le 10^5\).