A Thanos no le gustan los algoritmos de ordenación tradicionales.

Para una secuencia $a_1, a_2, \dots, a_m$ de longitud $m$, se define una operación de "ordenación de Thanos" de la siguiente manera:

• Si la secuencia actual ya es estrictamente creciente, es decir, $a_1 < a_2 < \dots < a_m$, el algoritmo termina inmediatamente.
• En caso contrario, se eligen exactamente $\lfloor m / 2 \rfloor$ de las $m$ posiciones de la secuencia actual de manera uniforme al azar y se eliminan. Se conserva el orden relativo de los elementos restantes y se continúa aplicando el mismo proceso a la secuencia restante.

Observa que $m$ en la eliminación anterior es la longitud actual de la secuencia, no la inicial. Es decir, si al comenzar una ronda quedan $m$ elementos y la secuencia todavía no está ordenada, en esa ronda se eliminan al azar $\lfloor m / 2 \rfloor$ de ellos.

Primero se genera uniformemente al azar una permutación $p_1, p_2, \dots, p_N$ de longitud $N$ y luego se le aplica la ordenación de Thanos.

Sea $X$ el número final de elementos restantes. Debes calcular $\mathbb{E}[X]$ e imprimir la respuesta módulo $998244353$.

Entrada

La entrada consiste en una sola línea con un entero $N$ $(1 \le N \le 10^6)$, que indica la longitud de la permutación inicial.

Salida

Imprime en una línea un entero que represente $\mathbb{E}[X]$ módulo $998244353$.

Más formalmente, si la expresión de $\mathbb{E}[X]$ como fracción irreducible es $\dfrac{P}{Q}$, debes imprimir $P \cdot Q^{-1} \bmod 998244353$, donde $Q^{-1}$ es el inverso multiplicativo de $Q$ módulo $998244353$.

Se puede demostrar que este inverso siempre existe dentro de las restricciones del problema.

Ejemplos

Entrada 1

2

Salida 1

499122178

Entrada 2

4

Salida 2

83187031

Nota

• Una "permutación" es una secuencia formada por los $N$ enteros distintos $1, 2, \dots, N$.
• Todas las elecciones aleatorias son uniformes entre todas las posibilidades válidas.
• Al eliminar elementos, se conserva el orden relativo de los elementos restantes.

Solo hay dos permutaciones de longitud $2$:

• $[1, 2]$: la secuencia ya está ordenada, así que quedan $2$ elementos al final.
• $[2, 1]$: la secuencia no está ordenada y se debe eliminar $1$ elemento al azar. Se elimine el que se elimine, la secuencia restante tiene longitud $1$ y está necesariamente ordenada, por lo que queda $1$ elemento al final.

Por tanto, $\mathbb{E}[X] = \frac{2 + 1}{2} = \frac{3}{2}$.

Módulo $998244353$, $\frac{3}{2} \equiv 3 \cdot 2^{-1} \equiv 499122178 \pmod{998244353}.$