Cho một số nguyên dương \(N\), ta định nghĩa một hoán vị của \(N\) số nguyên dương đầu tiên là \(P_1,P_2,…,P_N\) thỏa mãn \(1≤P_i≤N\) và \(P_i≠P_j\) nếu \(i≠j\).

Yêu cầu:

• Hãy đếm số lượng hoán vị của \(N\) số nguyên dương đầu tiên mà \(P_i≠i\).

Input:

• Gồm một dòng duy nhất chứa số nguyên dương \(N (N≤10^6)\).

Output:

• In ra kết quả bài toán khi chia lấy dư cho \((10^9+7)\).

Example