题目描述

程序中有一个初始值为 $0$ 的整数变量 $x$，以及 $N$ 个线程。每个线程都要执行一次语句

x = x + 1

但这条语句实际上分为两个步骤：

1. 线程读取当前的 $x$，并把该值记在自己的局部存储中；
2. 线程把自己记住的值加 $1$，再写回到 $x$。

同一线程的步骤 1 必须先于步骤 2，但在这两个步骤之间，其他线程可以执行自己的操作。

例如，线程 A 和 B 都先读取 $x=0$，之后二者都写回 $1$，最终 $x$ 只会变成 $1$，而不是 $2$。

现在你可以任意安排这 $2N$ 次操作的顺序。每个线程恰好被执行两次：第一次执行读取步骤，第二次执行写入步骤。

满足每个线程“先读后写”的合法执行顺序共有

种。

对于每一个可能的最终值 $x$，求有多少种合法线程执行顺序会得到该值。

输入格式

输入一个整数 $N$。

输出格式

第一行输出可能的最终值个数 $M$。

接下来输出 $M$ 行，每行包含两个整数：

• 一个可能的最终值 $x$；
• 得到该最终值的合法线程执行顺序数，对 $998244353$ 取模后的结果。

按照最终值 $x$ 从小到大输出。

其中

是质数。

样例 1

输入

2

输出

2
1 4
2 2

样例 2

输入

100

输出

100
... [省略 89 行] ...
90 729889561
91 145721628
92 477239109
... [省略 8 行] ...

说明

设两个线程为 A、B，其读取和写入步骤分别记为 A1、A2、B1、B2。所有合法顺序及最终结果如下：

• 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 的完整输出过长，题面中仅展示了一部分；实际输出时不能省略任何行。