AIが世界を席巻する中、LGエレクトロニクスはAI CPUを搭載したノートパソコン「LG gram」、部屋の環境を自ら調節するエアコン「Whisen AI AIR」など、AIを活用した次世代電子機器の開発に全力を注いでいる。

このような高性能なAI演算を可能にする技術として、マルチスレッディングは欠かせない。スレッドとはプログラム内で並列に動作する実行経路を意味し、コンピュータはこれを通じて複数の作業を同時に行うことで効率性を向上させる。しかし、スレッド間で共有されるリソースがある場合には、同期を慎重に合わせる必要がある。

スレッドを学んだばかりのプログラマ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を行うと、両方とも x に $1$ を書き込むため、x の値は $1$ になる。x を $1$ 増やす命令が二回実行されても、x が $2$ 増えるとは限らないのである。そのため、プログラムを実行した結果 x の値が $N$ ではなく別の数になっているのを見て、OOは驚くしかなかった。

今、私たちがLG gramになり、スレッド $N$個を望む順序で実行させることができると仮定しよう。各スレッドは正確に二回実行されなければならない。スレッドが最初に実行されるときは手順 1を行い、二回目に実行されるときは手順 2を行う。このようにスレッドを実行させる場合の数は $\frac{(2N)!}{2^N}$ である。それでは、x の初期値が $0$ であるとき、$N$個のスレッドが実行を終えたときに出現しうる x 値の分布はどうなるだろうか？

入力

一行目に整数 $N$ が与えられる。($1 \leq N \leq 200000$)

出力

一行目に可能な x 値の個数 $M$ を出力する。

次の行から $M$ 行にわたって、一行に一つずつ、可能な x 値と、その x 値が出現するスレッド実行の場合の数を $998244353$ で割った余りを出力する。可能な x 値が複数ある場合は、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は出力が非常に長いため、一部のみを表示した。実際には行を省略せずすべて出力しなければならない。