Cây tìm kiếm nhị phân sọc

Một cây tìm kiếm nhị phân là cây nhị phân có gốc, mỗi đỉnh lưu một khóa và có tối đa hai cây con: cây con trái và cây con phải. Khóa tại mỗi đỉnh phải lớn hơn mọi khóa trong cây con trái và nhỏ hơn mọi khóa trong cây con phải của nó.

Độ sâu của một đỉnh là số cạnh trên đường đi đơn từ đỉnh đó tới gốc; đặc biệt, độ sâu của gốc bằng $0$.

Ta gọi một cây tìm kiếm nhị phân là cân bằng hoàn hảo nếu không tồn tại cây tìm kiếm nhị phân nào có cùng số đỉnh mà tổng độ sâu của các đỉnh nhỏ hơn thực sự.

Ta gọi một cây tìm kiếm nhị phân với khóa nguyên là sọc nếu với mọi đỉnh $v$, cả hai điều kiện sau đều thỏa mãn:

• Nếu $v$ có cây con trái với gốc là $u$ thì khóa của $v$ và khóa của $u$ khác tính chẵn lẻ.
• Nếu $v$ có cây con phải với gốc là $w$ thì khóa của $v$ và khóa của $w$ cùng tính chẵn lẻ.

Cho một số nguyên $n$. Hãy đếm số cây tìm kiếm nhị phân vừa cân bằng hoàn hảo vừa sọc, có $n$ đỉnh với các khóa nguyên đôi một phân biệt nhận giá trị từ $1$ đến $n$. In kết quả theo modulo $998244353$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $n$ là số đỉnh cần có.

Dữ liệu ra

In ra một số nguyên duy nhất là số cây thỏa mãn, lấy phần dư khi chia cho $998244353$.

Ràng buộc

• $1\le n\le {10}^6$

Ví dụ