Hoán vị có chu trình

Một hoán vị độ dài $n$ là dãy gồm $n$ số nguyên phân biệt từ $1$ tới $n$. Với một hoán vị $p$ độ dài $n$, ta xây dựng đồ thị vô hướng $n$ đỉnh như sau:

• Với mỗi $1\le i\le n$, tìm $j$ lớn nhất thoả $1\le j<i$ và $p_j>p_i$, thêm cạnh $(i,j)$.
• Với mỗi $1\le i\le n$, tìm $j$ nhỏ nhất thoả $i<j\le n$ và $p_j>p_i$, thêm cạnh $(i,j)$.

(Nếu không tồn tại $j$ thoả mãn thì không thêm cạnh.)

Hoán vị $p$ được gọi là có chu trình nếu đồ thị tạo ra chứa ít nhất một chu trình đơn (có $\ge 3$ đỉnh phân biệt).

Cho $n$, đếm số hoán vị có chu trình modulo ${10}^9+7$.

Dữ liệu vào

Một dòng chứa số nguyên $n$ ($3\le n\le {10}^6$).

Dữ liệu ra

In ra một số nguyên — số hoán vị có chu trình modulo ${10}^9+7$.

Ràng buộc

• $3\le n\le {10}^6$.

Ví dụ