Expected Number of Layers

WD wants to buy (n) blocks. Each block has a height of 1 and its top‐view is a square (the side lengths may differ). Due to some special reasons, the seller assigns each block a random size and a label, and gives them to WD.

WD then groups blocks with equal size into a layer, and stacks all layers so that the sizes decrease from bottom to top (or equivalently, the layers are arranged in descending order of block sizes). Different stacking ways are defined by the property that there exists at least one block which appears in a different layer in the two stackings. Note that WD only cares about the relative sizes of the blocks, so instead of assuming that each block’s size is chosen independently from some distribution, all distinct stacking arrangements (i.e. all ordered partitions of the (n) blocks) are considered equally likely.

Let (F(n)) denote the total number of ordered partitions (also known as weak orders) of (n) objects, i.e., [ F(n) = \sum_{k=1}^{n} k!,S(n,k), ] where (S(n,k)) is the Stirling number of the second kind. Also, let [ A(n) = \sum_{k=1}^{n} k \cdot k!,S(n,k), ] then the expected number of layers is given by (E(n)=\frac{A(n)}{F(n)}).

Your task is to compute (E(n)) modulo (998244353). That is, if (F(n)) is not divisible by (998244353) (which is prime), output (E(n) \bmod 998244353) in the form (A(n) \cdot F(n)^{-1} \bmod 998244353).

inputFormat

The input is a single integer \(n\) (\(1 \le n \le N\)) representing the number of blocks.

outputFormat

Output a single integer which is the expected number of layers \(E(n)=\frac{A(n)}{F(n)}\) modulo \(998244353\).

sample

1

1