Colin a récemment reçu un cadeau d'Eva : un mystérieux générateur de suites croissantes de nombres aléatoires ! Il vous suffit d'entrer un entier strictement positif $n$, et le générateur vous renverra une suite croissante ! Après plusieurs essais, Colin a compris comment fonctionne le générateur.

Au départ, le générateur crée une nouvelle suite vide et choisit un nombre $k$ parmi $\{1, 2, \cdots, n\}$ de manière équiprobable.

Ensuite, le générateur choisit un nombre $x$ parmi $\{1, 2, \cdots, n\}$ de manière équiprobable comme premier élément de la suite.

Puis, le générateur répète le processus suivant :

• Si le plus grand élément de la suite est supérieur ou égal à $k$, le générateur s'arrête immédiatement et renvoie la suite déjà générée.
• Sinon, si le plus grand élément de la suite est $y$, alors le générateur choisit un nombre $x$ parmi $\{y + 1, y + 2, \cdots, n\}$ de manière équiprobable et ajoute $x$ à la fin de la suite.

Maintenant, Colin souhaite savoir, pour un entier $n$ donné, quelle est la longueur espérée de la suite renvoyée par le générateur ?

Entrée

Un seul entier $n$ ($1 \le n \le 10^7$).

Sortie

Un seul entier, représentant la longueur espérée modulo $998244353$.

Exemples

Entrée 1

3

Sortie 1

55458021

Remarque

• Si $k = 1$, la longueur espérée est $1$.
• Si $k = 2$, la longueur espérée est $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$
• Si $k = 3$, la longueur espérée est $1 \times \frac{1}{3} + 2 \times (\frac{1}{3} + \frac{1}{3} \times \frac{1}{2}) + 3 \times \frac{1}{3} \times \frac{1}{2} = \frac{11}{6}$

Ainsi, la réponse est $(1 + \frac{4}{3} + \frac{11}{6})/3 = \frac{25}{18}$.

L'inverse de $18$ modulo $998244353$ est $720954255$, donc le résultat affiché est $25 \times 720954255 \bmod 998244353 = 55458021$.