Vào dịp lễ tình nhân, anh chàng đào hoa Phú Lâm đã gửi ~n~ bức thư chúc mừng đến ~n~ người yêu của mình (giả sử tên của họ đều khác nhau). Tuy nhiên, đáng tiếc là Phú đã mắc nhầm lẫn không hề nhẹ nên đã gửi sai địa chỉ hết các bức thư, vì thế cô ~X~ thì nhận thư của cô ~Y~, cô ~Y~ thì nhận thư của cô ~Z~, ... Thế là sau đợt lễ đáng nhớ đó, cả ~n~ cô gái đã cùng chia tay Phú Lâm. Câu hỏi đặt ra là Phú có bao nhiêu cách thực hiện lỗi sai đó, tức là gửi thư cho các cô gái mà không ai nhận đúng lá thư của họ?

Input

Số nguyên dương ~n~ duy nhất với ~1 \le n \le 10^6.~

Output

Kết quả của bài toán, lấy modulo ~10^9+7.~

Sample input 1

4

Sample output 1

9

Sample input 2

12345

Sample output 2

137669039