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ị ~q~ được gọi là tuyệt vời nếu ~q_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~.

Input

Một số nguyên ~n~ là độ dài của hoán vị ~p~ (~2 \le n \le 2 \cdot 10^5~).

Output

Phần dư của đáp án khi chia cho ~998244353~.

Scoring

Sample Input 1

3

Sample Output 1

7

Sample Input 2

4

Sample Output 2

27

Sample Input 3

101206

Sample Output 3

160323547

Notes

Ở test ví dụ thứ nhất, với ~n = 3~ thì ta có ~6~ hoán vị là ~(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ị tương ứng trên thành hoán vị tuyệt vời là ~2, 1, 1, 0, 0, 1~. Tổng các ~f(p)^2~ là ~2^2 + 1^2 + 1^2 + 0^2 + 0^2 + 1^2 = 7~.