在 AI 席捲全球的浪潮下，LG 電子正全力投入開發搭載 AI CPU 的筆記型電腦 LG gram、能自動調節室內環境的空調 Whisen AI AIR 等運用 AI 技術的次世代電子產品。

多執行緒（multithreading）是實現這些高效能 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，兩者都會將 $1$ 寫入 x，因此 x 的最終值變為 $1$。即使將 x 加 $1$ 的指令執行了兩次，x 的值也未必會增加 $2$。因此，當 OO 執行程式後發現 x 的值不是 $N$ 時，感到非常驚訝。

現在，假設我們化身為 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 的輸出因過長而僅顯示部分。實際執行時，請勿省略任何行並完整輸出。