406882: GYM102599 A Долгая игра

A. Долгая играограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Леша очень любит играть с кубиками. Иногда он строит из них стены, иногда рисует на них буквы, а затем составляет слова, но сегодня особенный день, ведь к Леше в гости пришла Полина, поэтому Леша придумал новую игру.

Перед началом игры Леша достал из шкафа $$$N$$$ кубиков, после чего на каждом кубике написал число от $$$1$$$ до $$$N$$$. Разумеется, ни на каких двух кубиках Леша не написал одно и то же число.

После успешной подготовки к игре Леша надел на глаза повязку, благодаря которой он больше не видит кубики и числа, написанные на них. Далее Леша и Полина по очереди делают ходы, причем первым ходит Леша, ведь кубики принадлежат ему!

Своим первым ходом Леша случайно равновероятно перемешивает все лежащие перед ним кубики и выкладывает их в ряд. После этого Полина во время своего хода сообщает ему, какие кубики лежат на своем месте. Будем говорить, что кубик с написанным на нем числом $$$A$$$ лежит на своем месте, если слева от него находятся ровно $$$A - 1$$$ кубиков. Во время всех следующих ходов Леша не будет трогать кубики, которые лежат на своем месте.

Далее Леша снова перемешивает все кубики, которые лежат не на своих местах, а Полина сообщает ему, какие из них оказались на своем месте. Игра продолжается до тех пор, пока все кубики не окажутся на своих местах.

Перед началом игры Леше стало интересно, насколько много ходов ему придется сделать. Посчитайте математическое ожидание количества ходов Леши, с учетом первого хода.

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

В единственной строке записано целое число $$$N$$$ ($$$1 \leq N \leq 10^6$$$) — количество кубиков, которые есть у Леши.

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

Нетрудно показать, что ответ можно представить в виде несократимой дроби $$$\frac{P}{Q}$$$.

В качестве ответа выведите $$$P \cdot Q^{-1} \pmod{998\,244\,353}$$$.

ПримерыВходные данные

1

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

1

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

2

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

2

Примечание

В первом примере у Леши есть всего один кубик, который после его первого хода с вероятностью $$$1$$$ окажется на своем месте. Значит, математическое ожидание количества ходов Леши равно $$$1$$$.

Во втором примере у Леши есть два кубика. С вероятностью $$$\frac{1}{2}$$$ после первого же хода они оба окажутся на своих местах и игра закончится, и с вероятностью $$$\frac{1}{2}$$$ ни один из кубиков не окажется на своем месте, и Леша окажется в том же положении, что и в начале игры. Тогда можно понять, что вероятность того, что игра закончится ровно через $$$k$$$ ходов, равна $$$\frac{1}{2^{k}}$$$. Можно показать, что математическое ожидание этой случайной величины равно 2.

Напомним, что математическое ожидание случайной величины $$$X$$$ равно $$$$$$\sum \limits_i x_i \cdot P(X = x_i)$$$$$$

Здесь $$$P(X = x_i)$$$ — вероятность того, что значение случайной величины равно $$$x_i$$$, а $$$x_i$$$ — все возможные значения случайной величины.

Также напомним, что $$$Q \cdot Q^{-1} \equiv 1 \pmod{998\,244\,353}$$$.