Колин недавно получил подарок от Евы: загадочный генератор возрастающих случайных последовательностей чисел! Достаточно ввести натуральное число $n$, и генератор вернёт вам возрастающую последовательность! После многочисленных экспериментов Колин выяснил, как работает этот генератор.

Сначала генератор создаёт новую пустую последовательность и равновероятно выбирает число $k$ из $\{1, 2, \cdots, n\}$.

Затем генератор равновероятно выбирает число $x$ из $\{1, 2, \cdots, n\}$ в качестве первого элемента последовательности.

Затем генератор повторяет следующий процесс:

• Если максимальный элемент в последовательности больше или равен $k$, генератор немедленно прекращает работу и возвращает текущую уже сгенерированную последовательность.
• Иначе, если максимальный элемент в последовательности равен $y$, генератор равновероятно выбирает число $x$ из $\{y + 1, y + 2, \cdots, n\}$ и добавляет $x$ в конец последовательности.

Теперь Колин хочет узнать: для заданного $n$ каково математическое ожидание длины последовательности, возвращаемой генератором?

Входные данные

Одно целое число $n$ ($1 \le n \le 10^7$).

Выходные данные

Одно целое число — математическое ожидание длины по модулю $998244353$.

Примеры

Входные данные 1

3

Выходные данные 1

55458021

Примечание

• Если $k = 1$, то математическое ожидание длины равно $1$.
• Если $k = 2$, то математическое ожидание длины равно $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$.
• Если $k = 3$, то математическое ожидание длины равно $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}$.

Таким образом, ответ равен $(1 + \frac{4}{3} + \frac{11}{6})/3 = \frac{25}{18}$.

Обратный элемент к $18$ по модулю $998244353$ равен $720954255$, поэтому выводимый результат равен $25 \times 720954255 \bmod 998244353 = 55458021$.