Tại học viện ma thuật, hai pháp sư tài năng là Alice và Bob đang chuẩn bị ký kết một "Khế ước Ma pháp" để chia sẻ một kho báu vĩ đại.

Kho báu này bao gồm ~n - 1~ viên đá ma thuật khác nhau, được đánh số từ ~1, 2, 3, \dots, n-1~. Cường độ ma lực của viên đá thứ ~i~ chính là ~i + 1~ (tức là các viên đá có cường độ ma lực từ ~2~ đến ~n~).

Theo ghi chép cổ, mỗi mức cường độ ma lực được hình thành từ sự kết hợp của các "Cổ ngữ căn nguyên" - chính là các ước số nguyên tố của mức cường độ đó. Ví dụ, viên đá có cường độ ma lực ~12~ được hình thành từ cội nguồn ~2~ và cội nguồn ~3~.

Bây giờ, Alice và Bob mỗi người muốn chọn ra một tập hợp các viên đá mang về nghiên cứu. Tuy nhiên, Khế ước Ma pháp quy định rất nghiêm ngặt: Để tránh xảy ra một vụ nổ cộng hưởng phép thuật, tập hợp đá của Alice và tập hợp đá của Bob tuyệt đối không được chứa bất kỳ "Cổ ngữ căn nguyên" nào chung. Cụ thể hơn, nếu Alice chọn một viên đá có ma lực là ~x~ và Bob chọn một viên đá có ma lực là ~y~, thì ~x~ và ~y~ phải luôn nguyên tố cùng nhau.

Hãy tính xem có tổng cộng bao nhiêu cách khác nhau để Alice và Bob chọn đá ma thuật thỏa mãn Khế ước. Chú ý, một pháp sư có thể không lấy bất cứ viên đá nào.

Đầu vào

Một dòng chứa một số nguyên dương ~n~ (~2 \le n \le 500~).

Đầu ra

Một dòng chứa một số nguyên duy nhất là kết quả bài toán. Do kết quả có thể rất lớn, bạn chỉ cần đưa ra kết quả sau khi chia lấy dư cho ~998244353~.

Giới hạn

• Subtask ~1~ (~30%~ số điểm): ~2 \le n \le 30~.
• Subtask ~2~ (~20%~ số điểm): ~2 \le n \le 100~.
• Subtask ~3~ (~20%~ số điểm): ~2 \le n \le 200~.
• Subtask ~4~ (~30%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

4

Đầu ra

21