Trong bối cảnh AI đang càn quét thế giới, LG Electronics đang dồn toàn lực để tạo ra các thiết bị điện tử thế hệ tiếp theo sử dụng AI, chẳng hạn như máy tính xách tay LG Gram được trang bị CPU AI và máy điều hòa Whisen AI AIR có khả năng tự điều chỉnh môi trường trong phòng.

Đa luồng (multithreading) là một công nghệ không thể thiếu để hiện thực hóa các phép tính AI hiệu năng cao này. Luồng (thread) là một đường dẫn thực thi chạy song song trong chương trình, thông qua đó máy tính có thể thực hiện nhiều tác vụ cùng lúc để nâng cao hiệu quả. Tuy nhiên, khi có các tài nguyên được chia sẻ giữa các luồng, việc đồng bộ hóa cần phải được thực hiện một cách cẩn thận.

Lập trình viên OO, người vừa mới học về luồng, đã mở chiếc LG Gram của mình, khai báo một biến số nguyên x và viết một chương trình trong đó $N$ luồng cùng thực hiện câu lệnh x = x + 1. Để thực hiện câu lệnh cộng thêm $1$ vào x này, cần có thao tác đọc x và thao tác ghi x. Trên thực tế, hai thao tác này không xảy ra đồng thời mà diễn ra theo trình tự sau:

• Bước 1: Luồng đọc và ghi nhớ giá trị của x.
• Bước 2: Luồng cộng thêm $1$ vào giá trị đã ghi nhớ và ghi đè kết quả đó vào x.

Vấn đề nằm ở chỗ một luồng khác có thể can thiệp vào giữa Bước 1 và Bước 2 của một luồng đầu tiên. Giả sử giá trị ban đầu của x là $0$, nếu luồng A và B cùng thực hiện Bước 1, cả hai đều đọc và ghi nhớ giá trị $0$. Sau đó, nếu cả A và B cùng thực hiện Bước 2, cả hai đều ghi $1$ vào x, do đó giá trị của x trở thành $1$. Ngay cả khi lệnh tăng x thêm $1$ được thực hiện hai lần, x có thể không tăng thêm $2$. Vì vậy, OO đã rất ngạc nhiên khi chạy chương trình và thấy giá trị của x không phải là $N$ mà là một số khác.

Bây giờ, hãy giả sử chúng ta trở thành chiếc LG Gram và có thể thực hiện $N$ luồng theo bất kỳ thứ tự nào chúng ta muốn. Mỗi luồng phải được thực hiện chính xác hai lần. Lần đầu tiên luồng được thực hiện, nó sẽ tiến hành Bước 1, và lần thứ hai được thực hiện, nó sẽ tiến hành Bước 2. Số cách thực hiện các luồng như vậy là $\frac{(2N)!}{2^N}$. Vậy, nếu giá trị ban đầu của x là $0$, phân phối các giá trị x có thể nhận được sau khi $N$ luồng kết thúc thực thi là gì?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$. ($1 \leq N \leq 200000$)

Dữ liệu ra

Dòng đầu tiên in ra số lượng $M$ các giá trị x có thể đạt được.

Từ dòng tiếp theo, in ra $M$ dòng, mỗi dòng chứa một giá trị x có thể đạt được và số cách thực hiện các luồng để thu được giá trị x đó, lấy phần dư cho $998244353$. Nếu có nhiều giá trị x khả thi, hãy in tất cả theo thứ tự tăng dần của x.

$998\,244\,353 = 119 \times 2^{23} + 1$ là một số nguyên tố.

Ví dụ

Dữ liệu vào 1

2

Dữ liệu ra 1

2
1 4
2 2

Dữ liệu vào 2

100

Dữ liệu ra 2

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

Ghi chú

Gọi hai luồng là A và B, các bước của mỗi luồng lần lượt là A1, A2 và B1, B2. Giá trị của x theo thứ tự thực thi luồng như sau:

• A1 A2 B1 B2: $x = 2$
• A1 B1 A2 B2: $x = 1$ (Ví dụ này đã được sử dụng trong bài toán)
• A1 B1 B2 A2: $x = 1$
• B1 A1 A2 B2: $x = 1$
• B1 A1 B2 A2: $x = 1$
• B1 B2 A1 A2: $x = 2$

Ví dụ 2 có kết quả quá dài nên chỉ hiển thị một phần. Trên thực tế, bạn phải in ra đầy đủ tất cả các dòng mà không được lược bỏ.