{"raw_statement":[{"iden":"statement","content":"Леша очень любит играть с кубиками. Иногда он строит из них стены, иногда рисует на них буквы, а затем составляет слова, но сегодня особенный день, ведь к Леше в гости пришла Полина, поэтому Леша придумал новую игру.\n\nПеред началом игры Леша достал из шкафа $N$ кубиков, после чего на каждом кубике написал число от $1$ до $N$. Разумеется, ни на каких двух кубиках Леша не написал одно и то же число.\n\nПосле успешной подготовки к игре Леша надел на глаза повязку, благодаря которой он больше не видит кубики и числа, написанные на них. Далее Леша и Полина по очереди делают ходы, причем первым ходит Леша, ведь кубики принадлежат ему!\n\nСвоим первым ходом Леша случайно равновероятно перемешивает все лежащие перед ним кубики и выкладывает их в ряд. После этого Полина во время своего хода сообщает ему, какие кубики лежат на своем месте. Будем говорить, что кубик с написанным на нем числом $A$ лежит на своем месте, если слева от него находятся ровно $A -1$ кубиков. Во время всех следующих ходов Леша не будет трогать кубики, которые лежат на своем месте.\n\nДалее Леша снова перемешивает все кубики, которые лежат не на своих местах, а Полина сообщает ему, какие из них оказались на своем месте. Игра продолжается до тех пор, пока все кубики не окажутся на своих местах.\n\nПеред началом игры Леше стало интересно, насколько много ходов ему придется сделать. Посчитайте математическое ожидание количества ходов Леши, с учетом первого хода.\n\nВ единственной строке записано целое число $N$ ($1 <= N <= 10^6$) — количество кубиков, которые есть у Леши.\n\nНетрудно показать, что ответ можно представить в виде несократимой дроби $frac(P, Q)$.\n\nВ качестве ответа выведите $P dot.op Q^(-1) pmod 998 thin 244 thin 353$.\n\nВ первом примере у Леши есть всего один кубик, который после его первого хода с вероятностью $1$ окажется на своем месте. Значит, математическое ожидание количества ходов Леши равно $1$.\n\nВо втором примере у Леши есть два кубика. С вероятностью $frac(1, 2)$ после первого же хода они оба окажутся на своих местах и игра закончится, и с вероятностью $frac(1, 2)$ ни один из кубиков не окажется на своем месте, и Леша окажется в том же положении, что и в начале игры. Тогда можно понять, что вероятность того, что игра закончится ровно через $k$ ходов, равна $frac(1, 2^k)$. Можно показать, что математическое ожидание этой случайной величины равно 2.\n\nНапомним, что математическое ожидание случайной величины $X$ равно $$\\sum \\limits_i x_i \\cdot P(X = x_i)$$\n\nЗдесь $P (X = x_i)$ — вероятность того, что значение случайной величины равно $x_i$, а $x_i$ — все возможные значения случайной величины.\n\nТакже напомним, что $Q dot.op Q^(-1) equiv 1 pmod 998 thin 244 thin 353$.\n\n"},{"iden":"входные данные","content":"В единственной строке записано целое число $N$ ($1 <= N <= 10^6$) — количество кубиков, которые есть у Леши."},{"iden":"выходные данные","content":"Нетрудно показать, что ответ можно представить в виде несократимой дроби $frac(P, Q)$.В качестве ответа выведите $P dot.op Q^(-1) pmod 998 thin 244 thin 353$."},{"iden":"примеры","content":"Входные данные1\nВыходные данные1\nВходные данные2\nВыходные данные2\n"},{"iden":"примечание","content":"В первом примере у Леши есть всего один кубик, который после его первого хода с вероятностью $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 dot.op Q^(-1) equiv 1 pmod 998 thin 244 thin 353$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of cubes, labeled $ 1 $ to $ N $.  \nLet $ \\pi \\in S_N $ be a uniformly random permutation representing the initial arrangement of cubes.  \n\nA cube with label $ i $ is in its correct position if $ \\pi(i) = i $ (i.e., it is a fixed point).  \n\nIn each move:  \n- The player (Lesha) randomly permutes the subset of cubes **not** currently in their correct positions.  \n- After each permutation, the set of cubes now in correct positions is revealed and fixed for all future moves.  \n- The game ends when all cubes are in correct positions.  \n\nLet $ X_N $ be the random variable denoting the number of moves Lesha makes (including the first).  \n\n**Objective**  \nCompute $ \\mathbb{E}[X_N] \\mod 998244353 $, where the expectation is taken over all possible permutations and random shuffles in each step.  \n\n**Note**  \nThe process is equivalent to the following:  \nAt each step, Lesha randomly permutes the remaining misplaced elements. The game ends when all elements are fixed.  \nThis is equivalent to the expected number of iterations in a random permutation until all elements are fixed, where in each iteration, only non-fixed elements are resampled uniformly at random.  \n\nIt is known that:  \n$$\n\\mathbb{E}[X_N] = \\sum_{k=1}^N \\frac{1}{k}\n$$  \nThat is, the $ N $-th harmonic number $ H_N $.  \n\nThus, compute $ H_N = \\sum_{k=1}^N \\frac{1}{k} \\mod 998244353 $.","simple_statement":"Leha has N cubes, each with a unique number from 1 to N. He shuffles them randomly. In each turn, he keeps the cubes that are in their correct positions (cube with number A is correct if there are exactly A-1 cubes to its left), and shuffles the rest. He starts first. Find the expected number of his turns until all cubes are in place. Output the answer as P * Q^(-1) mod 998244353.","has_page_source":false}