在人工智能席卷全球的浪潮下，LG 电子正全力以赴开发利用 AI 的下一代电子产品，例如搭载 AI CPU 的笔记本电脑 LG gram，以及能自动调节室内环境的空调 Whisen AI AIR。

实现这些高性能 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$。因此，当 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 值及其对应的方案数（对 $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 的输出过长，此处仅显示部分。实际输出时请勿省略任何行。