CSES - Christmas Party | Bữa tiệc Giáng Sinh
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Có \(n\) đứa trẻ trong một bữa tiệc Giáng Sinh, và mỗi đứa trẻ đã mang theo một món quà. Ý tưởng đó là mọi người sẽ nhận được một món quà do ai đó khác mang đến.
Các món quà có thể được phân phối bằng nhiêu cách?
Input
- Dòng đầu vào duy nhất có một số nguyên \(n\): số lượng đứa trẻ.
Output
- In số lượng cách chia lấy dư cho \(10 ^ 9 + 7\).
Constraints
- \(1 \leq n \leq 10 ^ 6\)
Example
Sample input
4
Sample output
9
Bình luận
Hint (đơn giản hóa vấn đề)
Đếm số lượng hoán vị từ của dãy {1;2;3...;N-1;N} sao cho ko sao cho không có phần tử nào trong hoán vị đó ở đúng vị trí ban đầu của nó.