Alors que l'IA envahit le monde, LG Electronics met tout en œuvre pour créer des appareils électroniques de nouvelle génération utilisant l'IA, tels que les ordinateurs portables LG gram équipés de processeurs IA et les climatiseurs Whisen AI AIR qui ajustent eux-mêmes l'environnement de la pièce.

Le multithreading est une technologie incontournable pour permettre de tels calculs d'IA haute performance. Un thread désigne un chemin d'exécution s'exécutant en parallèle au sein d'un programme, et l'ordinateur améliore son efficacité en effectuant plusieurs tâches simultanément grâce à cela. Cependant, lorsque des ressources sont partagées entre les threads, une synchronisation minutieuse est nécessaire.

Le programmeur OO, qui vient d'apprendre le fonctionnement des threads, a ouvert son LG gram, déclaré une variable entière x, et écrit un programme dans lequel $N$ threads exécutent l'instruction x = x + 1. Pour exécuter cette instruction qui ajoute $1$ à x, il est nécessaire de lire x puis d'écrire dans x. En réalité, ces deux opérations ne se produisent pas simultanément, mais dans l'ordre suivant :

• Étape 1 : Le thread lit et mémorise la valeur de x.
• Étape 2 : Le thread ajoute $1$ à la valeur mémorisée et écrase x avec ce résultat.

Le problème est qu'un autre thread peut interférer entre l'étape 1 et l'étape 2 d'un thread donné. Si la valeur initiale de x est $0$, et que les threads A et B effectuent chacun l'étape 1, ils lisent et mémorisent tous deux la valeur $0$. Ensuite, si A et B effectuent chacun l'étape 2, ils écrivent tous deux $1$ dans x, ce qui fait que la valeur finale de x devient $1$. Même si l'instruction d'incrémentation de x est exécutée deux fois, il est possible que x n'augmente pas de $2$. C'est pourquoi OO a été surpris de constater, après avoir exécuté le programme, que la valeur de x était différente de $N$.

Imaginons maintenant que nous soyons le LG gram et que nous puissions exécuter les $N$ threads dans l'ordre de notre choix. Chaque thread doit être exécuté exactement deux fois. La première fois qu'un thread est exécuté, il effectue l'étape 1, et la deuxième fois, il effectue l'étape 2. Le nombre de façons d'exécuter les threads de cette manière est $\frac{(2N)!}{2^N}$. Alors, si la valeur initiale de x est $0$, quelle est la distribution des valeurs possibles de x une fois que les $N$ threads ont terminé leur exécution ?

Entrée

La première ligne contient un entier $N$. ($1 \leq N \leq 200000$)

Sortie

La première ligne contient le nombre $M$ de valeurs possibles pour x.

À partir de la ligne suivante, affichez $M$ lignes, chacune contenant une valeur possible de x et le nombre de façons d'exécuter les threads menant à cette valeur, modulo $998244353$. Si plusieurs valeurs de x sont possibles, affichez-les toutes par ordre croissant de x.

$998\,244\,353 = 119 \times 2^{23} + 1$ est un nombre premier.

Exemples

Entrée 1

2

Sortie 1

2
1 4
2 2

Entrée 2

100

Sortie 2

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

Remarque

Appelons les deux threads A et B, et notons les étapes de chaque thread A1, A2, B1 et B2. Les valeurs de x selon l'ordre d'exécution des threads sont les suivantes :

• A1 A2 B1 B2 : $x = 2$
• A1 B1 A2 B2 : $x = 1$ (cet exemple a été utilisé dans l'énoncé)
• A1 B1 B2 A2 : $x = 1$
• B1 A1 A2 B2 : $x = 1$
• B1 A1 B2 A2 : $x = 1$
• B1 B2 A1 A2 : $x = 2$

L'exemple 2 est trop long pour être affiché en entier. En réalité, vous devez afficher toutes les lignes sans en omettre aucune.