Cho một bảng vuông kích thước \( n \times n \), yêu cầu điền các số từ \( 1 \) đến \( n^2 \) sao cho mỗi số chỉ xuất hiện một lần và thỏa mãn ít nhất một trong hai điều kiện sau:

• Trong cùng một cột, tồn tại ô vuông có giá trị lớn hơn ô vuông đang xét.
• Trong cùng một hàng, tồn tại ô vuông có giá trị nhỏ hơn ô vuông đang xét.

Hãy tính số cách điền bảng thỏa mãn điều kiện trên.

Input

• Một số nguyên \(n\) duy nhất (\(1 \leq n \leq 1000\)).

Output

• Một số nguyên duy nhất là số cách điền bảng thỏa mãn điều kiện, modulo \(998244353\).

Sample Input

2

Sample Output

8

Sample Input

5

Sample Output

704332752

Sample Input

100

Sample Output

927703658