Cho một hoán vị p của các số nguyên từ 1 đến n. Bạn được thực hiện thao tác sau một số lần: Chọn một số nguyên i thỏa mãn ~1 \le i \le n-1~ và đổi giá trị của hai phần tử ~p_i~ và ~p_{i+1}~ cho nhau.

Một hoán vị p được gọi là tuyệt vời nếu ~p_i \ne i~ với mọi số nguyên i thỏa mãn ~1 \le i \le n~.

Gọi f(p) là số thao tác tối thiểu cần phải thực hiện để chuyển đổi hoán vị p thành một hoán vị tuyệt vời.

Yêu cầu

Hãy tính tổng của ~f(p)^2~ với mọi hoán vị p có thể. Vì tổng này có thể rất lớn, nên hãy in ra phần dư của đáp án khi chia cho 998244353.

Dữ liệu vào

Dòng duy nhất chứa số nguyên n là độ dài của hoán vị p.

Ràng buộc

• ~2 \le n \le 2 \times 10^5~.

Dữ liệu ra

In ra phần dư của đáp án khi chia cho 998244353.

Input 1

3

Output 1

7

Input 2

4

Output 2

27

Input 3

101206

Output 3

160323547

Giải thích

Ở ví dụ đầu tiên, với n = 3 có 6 hoán vị:

• $$(1,2,3)$$
• $$(1,3,2)$$
• $$(2,1,3)$$
• $$(2,3,1)$$
• $$(3,1,2)$$
• $$(3,2,1)$$

Số thao tác tối thiểu để chuyển các hoán vị trên thành hoán vị tuyệt vời lần lượt là: 2, 1, 1, 0, 0, 1.

Do đó: ~\sum f(p)^2 = 2^2 + 1^2 + 1^2 + 0^2 + 0^2 + 1^2 = 7.~

Giới hạn

• Subtask 1: 10% số điểm có ~n \le 10~
• Subtask 2: 10% số điểm có ~n \le 16~
• Subtask 3: 20% số điểm có ~n \le 300~
• Subtask 4: 30% số điểm có ~n \le 5000~
• Subtask 5: 30% số điểm không có ràng buộc gì thêm