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