Tháp phát sóng

Có $n+2$ thị trấn nằm trên trục số, được đánh số từ $0$ đến $n+1$. Thị trấn thứ $i$ nằm tại điểm $i$.

Tại mỗi thị trấn $1,2,\dots ,n$, một tháp phát sóng vô tuyến được xây dựng với xác suất ${\displaystyle \frac{1}{2}}$ (các sự kiện này độc lập). Sau đó, bạn muốn đặt công suất tín hiệu cho mỗi tháp là một số nguyên từ $1$ đến $n$ (các công suất không nhất thiết phải bằng nhau và cũng không nhất thiết phải khác nhau). Tín hiệu từ tháp đặt tại thị trấn $i$ với công suất $p$ phủ tới mọi thị trấn $c$ thỏa mãn $|c-i|<p$.

Sau khi xây xong các tháp, bạn muốn chọn công suất tín hiệu sao cho:

• Thị trấn $0$ và thị trấn $n+1$ không nhận được tín hiệu từ bất kỳ tháp nào;
• Mỗi thị trấn $1,2,\dots ,n$ nhận được tín hiệu từ đúng một tháp.

Hãy tính xác suất rằng sau khi xây các tháp, tồn tại cách đặt công suất tín hiệu thỏa mãn mọi ràng buộc trên.

Có thể chứng minh được xác suất cần tìm biểu diễn được dưới dạng phân số tối giản ${\displaystyle \frac{x}{y}}$. Hãy in ra $x·y^{-1}mod998244353$, trong đó $y^{-1}$ là số nguyên thỏa mãn $y·y^{-1}\equiv 1\left(\mathrm{mod}998244353\right)$.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên $n$.

Dữ liệu ra

In ra xác suất cần tìm theo modulo $998244353$.

Ràng buộc

• $1\le n\le 2·{10}^5$

Ví dụ