W dobie dominacji sztucznej inteligencji, firma LG Electronics wkłada ogromny wysiłek w tworzenie urządzeń elektronicznych nowej generacji wykorzystujących AI, takich jak laptopy LG gram z procesorami AI czy klimatyzatory Whisen AI AIR, które samodzielnie dostosowują warunki w pomieszczeniu.

Technologią umożliwiającą tak zaawansowane obliczenia AI jest wielowątkowość. Wątek to ścieżka wykonania działająca równolegle wewnątrz programu, dzięki której komputer może wykonywać wiele zadań jednocześnie, zwiększając tym samym wydajność. Jednak w przypadku współdzielenia zasobów między wątkami należy zachować szczególną ostrożność w kwestii synchronizacji.

Programista OO, który dopiero co poznał wielowątkowość, otworzył swojego laptopa LG gram, zadeklarował zmienną całkowitą x i napisał program, w którym $N$ wątków wykonuje instrukcję x = x + 1. Aby wykonać tę instrukcję, która zwiększa x o $1$, konieczne jest odczytanie wartości x oraz jej zapisanie. W rzeczywistości operacje te nie dzieją się jednocześnie, lecz w następującej kolejności:

• Krok 1: Wątek odczytuje i zapamiętuje wartość x.
• Krok 2: Wątek dodaje $1$ do zapamiętanej wartości i nadpisuje wynik w x.

Problem polega na tym, że między krokiem 1 a krokiem 2 jednego wątku może wystąpić ingerencja innego wątku. Przyjmując, że początkowa wartość x wynosi $0$, jeśli wątki A i B wykonają swoje kroki 1, oba odczytają i zapamiętają wartość $0$. Następnie, jeśli oba wątki wykonają swoje kroki 2, oba zapiszą w x wartość $1$, przez co końcowa wartość x wyniesie $1$. Nawet jeśli instrukcja zwiększająca x o $1$ zostanie wykonana dwukrotnie, x nie musi zwiększyć się o $2$. Dlatego OO był bardzo zaskoczony, gdy po uruchomieniu programu wartość x okazała się inna niż $N$.

Wyobraźmy sobie teraz, że stajemy się laptopem LG gram i możemy uruchamiać kroki $N$ wątków w dowolnej kolejności. Każdy wątek musi zostać wykonany dokładnie dwa razy. Gdy wątek jest uruchamiany po raz pierwszy, wykonuje krok 1, a gdy po raz drugi – krok 2. Liczba sposobów na uruchomienie wątków w ten sposób wynosi $\frac{(2N)!}{2^N}$. Jaki będzie rozkład możliwych wartości x po zakończeniu wykonywania wszystkich $N$ wątków, przy założeniu, że początkowa wartość x wynosi $0$?

Wejście

W pierwszej linii podano liczbę całkowitą $N$. ($1 \leq N \leq 200000$)

Wyjście

W pierwszej linii należy wypisać liczbę możliwych wartości x, oznaczmy ją jako $M$.

W kolejnych $M$ liniach należy wypisać po jednej parze liczb: możliwą wartość x oraz liczbę sposobów, na jakie można uzyskać tę wartość, modulo $998244353$. Jeśli istnieje wiele możliwych wartości x, należy je wypisać w kolejności rosnącej.

$998\,244\,353 = 119 \times 2^{23} + 1$ jest liczbą pierwszą.

Przykład

Wejście 1

2

Wyjście 1

2
1 4
2 2

Wejście 2

100

Wyjście 2

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

Uwagi

Niech dwa wątki nazywają się A i B, a ich kroki odpowiednio A1, A2 oraz B1, B2. Wartości x w zależności od kolejności wykonywania kroków są następujące:

• A1 A2 B1 B2: $x = 2$
• A1 B1 A2 B2: $x = 1$ (przykład użyty w treści zadania)
• A1 B1 B2 A2: $x = 1$
• B1 A1 A2 B2: $x = 1$
• B1 A1 B2 A2: $x = 1$
• B1 B2 A1 A2: $x = 2$

W przykładzie 2 wyjście jest zbyt długie, więc pokazano tylko jego fragment. W rzeczywistości należy wypisać wszystkie linie bez pomijania żadnej z nich.