Alice vừa nhận được một cây đàn ma thuật với ~N~ phím đàn, được đánh số từ ~1~ đến ~N~. Mỗi phím đàn khi bấm sẽ phát ra một âm thanh có độ mê hoặc tương ứng với số thứ tự của phím đó (ví dụ, phím số ~1~ có độ mê hoặc là ~1~, phím số ~2~ có độ mê hoặc là ~2~, v.v.).

Alice háo hức muốn sáng tác các bản nhạc đặc biệt, trong đó tổng độ mê hoặc của các phím đàn trong bản nhạc đúng bằng ~N~.

Alice muốn nhờ bạn tính toán số lượng bản nhạc khác nhau cô ấy có thể sáng tác. Vì số lượng bản nhạc có thể rất lớn hãy in đáp án theo modulo ~998\;244\;353~.

Input

• Dòng duy nhất chứa số nguyên dương ~N~ ~(1 \leq N \leq 10^{12})~.

Output

• Dòng duy nhất chứa số nguyên dương là số bản nhạc khác nhau mà Alice có thể sáng tác sao cho tổng độ mê hoặc bằng ~N~.

Scorint

• Subtask 1 (40% số điểm): Với ~N \leq 20~.
• Subtask 2 (40% số điểm): Với ~N \leq 3\times 10^3~.
• Subtask 3 (20% số điểm): Không có ràng buộc gì thêm.

Samples

Sample Input

3

Sample Output

4

Notes

Có ~4~ bản nhạc khác nhau với tổng độ mê hoặc bằng ~3~:

• Chơi phím ~1 \rightarrow 1 \rightarrow 1~, tổng độ mê hoặc: ~1 + 1 + 1 = 3~.
• Chơi phím ~1 \rightarrow 2~, tổng độ mê hoặc: ~1 + 2 = 3~.
• Chơi phím ~2 \rightarrow 1~, tổng độ mê hoặc: ~2 + 1 = 3~.
• Chơi phím ~3~, tổng độ mê hoặc: ~3~.