В то время как ИИ захватывает мир, LG Electronics прилагает все усилия для создания электроники следующего поколения, использующей возможности ИИ, такой как ноутбуки LG gram с ИИ-процессорами и кондиционеры Whisen AI AIR, способные самостоятельно регулировать микроклимат в помещении.

Технологией, делающей возможными столь высокопроизводительные вычисления ИИ, является многопоточность. Поток — это путь выполнения, работающий параллельно внутри программы, и компьютер повышает эффективность, выполняя несколько задач одновременно с помощью потоков. Однако при наличии общих ресурсов между потоками необходимо тщательно следить за синхронизацией.

Программист OO, только что изучивший потоки, открыл свой LG gram, объявил целочисленную переменную x и написал программу, в которой $N$ потоков выполняют инструкцию x = x + 1. Чтобы выполнить эту инструкцию, увеличивающую x на $1$, требуются операции чтения x и записи x. На самом деле эти две операции не происходят одновременно, а выполняются в следующем порядке:

• Шаг 1: Поток считывает и запоминает значение x.
• Шаг 2: Поток прибавляет $1$ к запомненному значению и записывает результат обратно в x.

Проблема заключается в том, что между Шагом 1 и Шагом 2 одного потока может вмешаться другой поток. Если начальное значение x равно $0$, и потоки A и B выполняют Шаг 1, оба считывают и запоминают значение $0$. После этого, если потоки A и B выполняют Шаг 2, оба записывают $1$ в x, в результате чего значение x становится равным $1$. Даже если команда увеличения x на $1$ была выполнена дважды, x может не увеличиться на $2$. Поэтому OO был крайне удивлен, когда после запуска программы значение x оказалось не равным $N$.

Теперь представим, что мы стали LG gram и можем выполнять $N$ потоков в любом желаемом порядке. Каждый поток должен быть выполнен ровно два раза. При первом выполнении поток совершает Шаг 1, а при втором — Шаг 2. Количество способов выполнения потоков таким образом равно $\frac{(2N)!}{2^N}$. Итак, если начальное значение x равно $0$, каким будет распределение возможных значений x после завершения работы $N$ потоков?

Входные данные

В первой строке дано целое число $N$ ($1 \leq N \leq 200000$).

Выходные данные

В первой строке выведите количество возможных значений x, обозначим его $M$.

В следующих $M$ строках выведите по одному возможному значению x и количество способов выполнения потоков, приводящих к этому значению, взятое по модулю $998244353$. Если существует несколько возможных значений x, выводите их в порядке возрастания.

$998\,244\,353 = 119 \times 2^{23} + 1$ является простым числом.

Примеры

Входные данные 1

2

Выходные данные 1

2
1 4
2 2

Входные данные 2

100

Выходные данные 2

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

Примечание

Пусть два потока называются A и B, а их шаги — A1, A2 и B1, B2 соответственно. Значения x в зависимости от порядка выполнения потоков:

• A1 A2 B1 B2: $x = 2$
• A1 B1 A2 B2: $x = 1$ (этот пример использовался в условии)
• A1 B1 B2 A2: $x = 1$
• B1 A1 A2 B2: $x = 1$
• B1 A1 B2 A2: $x = 1$
• B1 B2 A1 A2: $x = 2$

Вывод для примера 2 сокращен из-за его большой длины. В решении необходимо вывести все строки без пропусков.