Colin niedawno otrzymał od Evy prezent: tajemniczy generator rosnących ciągów liczb losowych! Wystarczy podać dodatnią liczbę całkowitą $n$, a generator zwróci rosnący ciąg! Po wielokrotnych eksperymentach Colin ustalił, jak działa generator.
Początkowo generator tworzy nowy pusty ciąg i wybiera z równym prawdopodobieństwem liczbę $k$ ze zbioru $\{1, 2, \cdots, n\}$.
Następnie generator wybiera z równym prawdopodobieństwem liczbę $x$ ze zbioru $\{1, 2, \cdots, n\}$ jako pierwszy element ciągu.
Następnie generator powtarza następujący proces:
- Jeśli największy element w ciągu jest większy lub równy $k$, generator natychmiast kończy działanie i zwraca wygenerowany dotychczas ciąg.
- W przeciwnym razie, jeśli największy element w ciągu wynosi $y$, generator wybiera z równym prawdopodobieństwem liczbę $x$ ze zbioru $\{y + 1, y + 2, \cdots, n\}$ i dołącza $x$ na koniec ciągu.
Teraz Colin chce wiedzieć, jaka jest oczekiwana długość ciągu zwróconego przez generator dla danego $n$?
Wejście
Pojedyncza liczba całkowita $n$ ($1 \le n \le 10^7$).
Wyjście
Pojedyncza liczba całkowita, oznaczająca oczekiwaną długość modulo $998244353$.
Przykład
Wejście 1
3
Wyjście 1
55458021
Uwagi
- Jeśli $k = 1$, oczekiwana długość wynosi $1$.
- Jeśli $k = 2$, oczekiwana długość wynosi $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$
- Jeśli $k = 3$, oczekiwana długość wynosi $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}$
Zatem odpowiedzią jest $(1 + \frac{4}{3} + \frac{11}{6})/3 = \frac{25}{18}$.
Odwrotność liczby $18$ modulo $998244353$ wynosi $720954255$, więc wynikiem wyjściowym jest $25 \times 720954255 \bmod 998244353 = 55458021$.