Nguồn đề: https://codeforces.com/contest/1391/problem/C

Một hoán vị có độ dài n là một mảng gồm n số nguyên phân biệt từ 1 đến n có thứ tự bất kì.

Xem xét một hoán vị p độ dài n, chúng ta sẽ xây dựng một đồ thị có n đỉnh bằng hai chuỗi thao tác sau:

• Với mỗi i ~( 1 \leq i \leq n)~, tìm j lớn nhất sao cho ~ 1 \leq j < i~ và ~ p_j > p_i ~, ta thêm 1 cạnh vô hướng giữa đỉnh i và đỉnh j.

• Với mỗi i ~( 1 \leq i \leq n)~, tìm j bé nhất sao cho ~ i < j \leq n~ và ~ p_j > p_i ~, ta thêm 1 cạnh vô hướng giữa đỉnh i và đỉnh j.

Trong trường hợp không tồn tại j, chúng ta không thêm cạnh.

Ví dụ: n = 4, p = [3, 1, 4, 2], các cạnh đồ thị ta thêm là (1,3), (2,1), (2,3), (4,3).

Một hoán vị được gọi là đẹp nếu, từ hoán vị đó ta xây dựng được một đồ thị có ít nhất một chu trình đơn giản - simple cycle.

Cho n hãy tìm số lượng các hoán vị đẹp có độ dài n. Kết quả có thể rất lớn hãy chia dư cho ~10^9 + 7~.

Input

Dòng 1: Chứa một số nguyên n ~(3 \leq n \leq 10^6)~

Kết quả

In ra số lượng các hoán vị đẹp có độ dài n, chia dư cho ~10^9 + 7~

Sample Input 1

4

Sample Output 1

16

Sample Input 2

583291

Sample Output 2

135712853

Giải thích

Có 16 hoán vị đẹp có độ dài bằng 4. Ví dụ một trong số đó là [4, 2, 1, 3], có một chu trình độ dài 4: 4 -> 3 -> 2 -> 1 -> 4

Các đỉnh ~v_1, v_2, ..., v_k~ tạo thành một chu trình đơn giản nếu thỏa mãn các điều kiện sau:

• ~ k \ge 3~
• ~v_i \ne v_j ~ với mọi cặp i,j. ~ 1 \leq i < j \leq k~
• Có một cạnh giữa ~v_i ~ và ~ v_{i+1} ~ với mọi ~ 1 <= i < k~
• Có một cạnh giữa ~v_1 ~ và ~ v_k ~.