Ban là một thiên tài học tập, không chỉ giỏi sinh, tin, toán và bây giờ Ban còn bắt đầu với con đường thiên văn học. Hôm nay là một ngày đẹp trời và Ban quyết định sẽ học về các chòm sao trên trời, trong lúc đang nghiên cứu thì Ban phát hiện một chòm sao rất thú vị đó là tập hợp các ngôi sao đứng thành vòng tròn mang tên H32. Khi Ban tìm kiếm trên mạng lại không thể tìm ra một hình dạng thống nhất về chòm sao này khi được biểu diễn bằng các đường nối giữa tất cả ngôi sao.

Ban thử hỏi liệu sẽ có bao nhiêu hình dạng bằng đường nối tồn tại sau khi đã chia dư cho ~10^9 + 7~, khi biết rằng các đường nối sẽ đi qua tất cả các ngôi sao và không cắt lên nhau

Input

• Một số nguyên duy nhất là ~N (1 \leq N \leq 10^9)~, đại diện cho số lượng ngôi sao

Output

• Một số nguyên duy nhất ~X~ là số lượng hình dạng bằng đường nối của chòm sao tồn tại.

Sample Input

4

Sample Output

8