Gọi LIS của một hoán vị là độ dài của dãy con tăng dài nhất của nó.

Một hoán vị được gọi là tốt (good) nếu có thể tìm được hai dãy con tăng có độ dài bằng LIS mà không có bất kỳ phần tử chung nào.

Cho $n$, hãy tìm số lượng hoán vị tốt với $n$ phần tử. Vì kết quả có thể rất lớn, bạn chỉ cần tìm kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 75$): số lượng phần tử.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng hoán vị tốt với $n$ phần tử, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

6

Dữ liệu ra 1

132