Có \(n\) người và \(n\) mũ, mỗi người có đúng 1 mũ ưa thích. Đếm số cách phân phát mũ sao cho không ai nhận đúng mũ mình thích (derangement). Kết quả modulo \(10^9+7\).

Định dạng đầu vào

• Một dòng chứa \(n\) (\(1 \le n \le 10^6\)).

Định dạng đầu ra

• Một số nguyên là số derangement modulo \(10^9+7\).

Ví dụ

Input:

4

Output:

9

Ràng buộc

• 100% số điểm: \(n \le 10^6\).