Một gia tộc cổ được chia thành hai nhánh.

• Nhánh thứ nhất gồm các thành viên được đánh số: \(1,3,5,\ldots\)

• Nhánh thứ hai gồm các thành viên được đánh số: \(2,4,6,\ldots\)

Trong buổi lễ truyền thừa, các thành viên của hai nhánh sẽ lần lượt tiến vào đại điện để xếp thành một hàng.

Để giữ gìn truyền thống của gia tộc, thứ tự xuất hiện của các thành viên trong mỗi nhánh không được thay đổi. Nói cách khác:

• Các thành viên của nhánh thứ nhất luôn xuất hiện theo đúng thứ tự:\(1,3,5,\ldots\)
• Các thành viên của nhánh thứ hai luôn xuất hiện theo đúng thứ tự:\(2,4,6,\ldots\)

Tuy nhiên, hai nhánh có thể được đan xen với nhau theo bất kỳ cách nào.

Gia tộc còn có một quy tắc đặc biệt: hai thành viên đứng cạnh nhau chỉ được phép xuất hiện nếu hiệu tuyệt đối giữa hai số hiệu của họ là một số nguyên tố.

Ngoài ra, nghi lễ có thể được tổ chức theo hai hướng (từ đầu đến cuối hoặc từ cuối về đầu), và hai cách này được xem là khác nhau nếu tạo ra hai dãy khác nhau.

Cho số nguyên dương \(n\).

Hãy giúp ledinhbaonam tính số lượng cách xếp hợp lệ của các thành viên được đánh số từ \(1\) đến \(n\).

Do đáp án rất lớn, hãy in kết quả chia lấy dư cho \(998244353\)

Input

• Gồm một số nguyên \(n\) (\(1\le n\le3\cdot10^4\))

Output

• In ra số lượng cách xếp hợp lệ modulo \(998244353\).

Example

1

1

4

2