Mientras la IA arrasa en el mundo, LG Electronics se esfuerza al máximo para crear dispositivos electrónicos de próxima generación que aprovechen la IA, como la computadora portátil LG gram con CPU de IA y el aire acondicionado Whisen AI AIR que ajusta automáticamente el entorno de la habitación.

El multihilo es una tecnología indispensable para hacer posibles estas operaciones de IA de alto rendimiento. Un hilo (thread) se refiere a una ruta de ejecución que corre en paralelo dentro de un programa, y a través de esto, la computadora mejora la eficiencia al realizar múltiples tareas simultáneamente. Sin embargo, cuando hay recursos compartidos entre hilos, se debe tener cuidado con la sincronización.

El programador OO, quien acaba de aprender sobre hilos, abrió su LG gram, declaró una variable entera x y escribió un programa donde $N$ hilos ejecutan la instrucción x = x + 1. Para ejecutar esta instrucción que suma $1$ a x, se requiere una operación de lectura de x y una operación de escritura de x. De hecho, estas dos no ocurren simultáneamente, sino en el siguiente orden:

• Procedimiento 1: El hilo lee y memoriza el valor de x.
• Procedimiento 2: El hilo suma $1$ al valor que memorizó y sobrescribe el resultado en x.

El problema es que otro hilo puede interferir entre el Procedimiento 1 y el 2 de un hilo. Si el valor inicial de x es $0$, cuando los hilos A y B realizan el Procedimiento 1, ambos leen y memorizan el valor $0$. Después, cuando A y B realizan el Procedimiento 2, ambos escriben $1$ en x, por lo que el valor final de x es $1$. Incluso si la instrucción de incrementar x se ejecuta dos veces, es posible que x no aumente en $2$. Por eso, OO se sorprendió al ver que, al ejecutar el programa, el valor de x era un número distinto de $N$.

Ahora, imaginemos que nos convertimos en la LG gram y podemos ejecutar los $N$ hilos en el orden que queramos. Cada hilo debe ejecutarse exactamente dos veces. La primera vez que se ejecuta un hilo, realiza el Procedimiento 1, y la segunda vez que se ejecuta, realiza el Procedimiento 2. El número de formas de ejecutar los hilos de esta manera es $\frac{(2N)!}{2^N}$. Entonces, si el valor inicial de x es $0$, ¿cuál es la distribución de los posibles valores de x cuando los $N$ hilos terminan su ejecución?

Entrada

En la primera línea se da un entero $N$. ($1 \leq N \leq 200000$)

Salida

En la primera línea, imprime el número de posibles valores de x, denotado como $M$.

A partir de la siguiente línea, imprime en $M$ líneas, una por línea, un posible valor de x y el número de formas de ejecución de los hilos que resultan en ese valor de x, módulo $998244353$. Si hay varios valores posibles de x, imprímelos todos en orden ascendente respecto al valor de x.

$998\,244\,353 = 119 \times 2^{23} + 1$ es un número primo.

Ejemplos

Entrada 1

2

Salida 1

2
1 4
2 2

Entrada 2

100

Salida 2

100
... [89 more lines] ...
90 729889561
91 145721628
92 477239109
... [8 more lines] ...

Nota

Llamemos a los dos hilos A y B, y a los pasos de cada hilo A1, A2, B1 y B2. Los valores de $x$ según el orden de ejecución de los hilos son los siguientes:

• A1 A2 B1 B2: $x = 2$
• A1 B1 A2 B2: $x = 1$ (este ejemplo se utilizó en el texto)
• A1 B1 B2 A2: $x = 1$
• B1 A1 A2 B2: $x = 1$
• B1 A1 B2 A2: $x = 1$
• B1 B2 A1 A2: $x = 2$

El ejemplo 2 se muestra parcialmente debido a que la salida es demasiado larga. En la práctica, se deben imprimir todas las líneas sin omitir ninguna.