As AI sweeps the world, LG Electronics is putting its full effort into creating next-generation electronic devices that utilize AI, such as the LG Gram laptop equipped with an AI CPU and the Whisen AI AIR air conditioner that autonomously adjusts room environments.

Multithreading is an essential technology that enables such high-performance AI computations. A thread refers to an execution path running in parallel within a program, and computers use this to improve efficiency by performing multiple tasks simultaneously. However, when there are shared resources between threads, synchronization must be handled with care.

A programmer named OO, who has just learned about threads, opened an LG Gram, declared an integer variable x, and wrote a program where $N$ threads execute the statement x = x + 1. Executing this statement, which adds $1$ to x, requires reading x and writing to x. In reality, these two operations do not happen simultaneously but occur in the following order:

• Step 1: The thread reads and remembers the value of x.
• Step 2: The thread adds $1$ to the value it remembered and overwrites x with the result.

The problem is that another thread can interfere between Step 1 and Step 2 of a thread. Assuming the initial value of x is $0$, if threads A and B both perform Step 1, they both read and remember the value $0$. After that, if A and B both perform Step 2, they both write $1$ to x, resulting in x becoming $1$. Even though the command to increment x is executed twice, x may not increase by $2$. Thus, OO was surprised to find that after running the program, the value of x was something other than $N$.

Now, let us assume we are the LG Gram and can execute the $N$ threads in any order we choose. Each thread must be executed exactly twice. The first time a thread is executed, it performs Step 1, and the second time it is executed, it performs Step 2. The number of ways to execute the threads in this manner is $\frac{(2N)!}{2^N}$. Given that the initial value of x is $0$, what is the distribution of possible values of x after all $N$ threads have finished execution?

Input

The first line contains an integer $N$. ($1 \leq N \leq 200000$)

Output

The first line should output the number of possible values of x, denoted as $M$.

Starting from the next line, output $M$ lines, each containing a possible value of x and the number of ways to execute the threads that result in that value, modulo $998244353$. If there are multiple possible values for x, output them in ascending order.

$998\,244\,353 = 119 \times 2^{23} + 1$ is a prime number.

Examples

Input 1

2

Output 1

2
1 4
2 2

Input 2

100

Output 2

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

Note

Let the two threads be A and B, and let the steps for each thread be A1, A2, B1, and B2. The values of $x$ based on the thread execution order are as follows:

• A1 A2 B1 B2: $x = 2$
• A1 B1 A2 B2: $x = 1$ (This example was used in the description.)
• A1 B1 B2 A2: $x = 1$
• B1 A1 A2 B2: $x = 1$
• B1 A1 B2 A2: $x = 1$
• B1 B2 A1 A2: $x = 2$

Example 2 is partially displayed because the output is too long. In reality, you must output all lines without omitting any.