Colin gần đây đã nhận được một món quà từ Eva: một máy tạo dãy số ngẫu nhiên tăng dần bí ẩn! Bạn chỉ cần nhập một số nguyên dương $n$, và máy tạo sẽ trả về một dãy tăng dần cho bạn! Sau nhiều lần thử nghiệm lặp đi lặp lại, Colin đã tìm ra cách máy tạo này hoạt động.

Ban đầu, máy tạo sẽ tạo một dãy rỗng mới và chọn một số $k$ từ $\{1, 2, \dots, n\}$ với xác suất bằng nhau.

Sau đó, máy tạo sẽ chọn một số $x$ từ $\{1, 2, \dots, n\}$ với xác suất bằng nhau làm phần tử đầu tiên của dãy.

Tiếp theo, máy tạo sẽ lặp lại quá trình sau:

• Nếu phần tử lớn nhất trong dãy lớn hơn hoặc bằng $k$, máy tạo sẽ dừng hoạt động ngay lập tức và trả về dãy hiện tại đã được tạo.
• Ngược lại, nếu phần tử lớn nhất trong dãy là $y$, thì máy tạo sẽ chọn một số $x$ từ $\{y + 1, y + 2, \dots, n\}$ với xác suất bằng nhau và thêm $x$ vào cuối dãy.

Bây giờ Colin muốn biết, với một số nguyên $n$ cho trước, kỳ vọng độ dài của dãy mà máy tạo trả về là bao nhiêu?

Dữ liệu vào

Một số nguyên duy nhất $n$ ($1 \le n \le 10^7$).

Dữ liệu ra

Một số nguyên duy nhất, biểu thị kỳ vọng độ dài theo modulo $998244353$.

Ví dụ

Dữ liệu vào 1

3

Dữ liệu ra 1

55458021

Ghi chú

• Nếu $k = 1$, kỳ vọng độ dài là $1$.
• Nếu $k = 2$, kỳ vọng độ dài là $1 \times \frac{2}{3} + 2 \times \frac{1}{3} = \frac{4}{3}$
• Nếu $k = 3$, kỳ vọng độ dài là $1 \times \frac{1}{3} + 2 \times (\frac{1}{3} + \frac{1}{3} \times \frac{1}{2}) + 3 \times \frac{1}{3} \times \frac{1}{2} = \frac{11}{6}$

Do đó, đáp án là $(1 + \frac{4}{3} + \frac{11}{6}) / 3 = \frac{25}{18}$.

Nghịch đảo của $18$ theo modulo $998244353$ là $720954255$, do đó kết quả xuất ra là $25 \times 720954255 \bmod 998244353 = 55458021$.