Kichirou là một cậu bé đam mê toán học và thích khám phá những con số bí ẩn. Tình cờ, trong một lần đang tìm hiểu về dãy số thì Kichirou phát hiện ra một công thức ~S(n)~ kỳ lạ. Công thức này yêu cầu tính tổng của các tổng từ ~1~ đến một số nguyên dương ~n~. Nhưng vì kết quả của bài toán này sẽ rất lớn, vì vậy Kichirou cần lấy phần dư của nó khi chia cho ~10^9 + 7~. Công thức tính ~S(n)~ như sau:

$$\displaystyle S(n) = \sum_{i = 1} ^ n (\sum_{j = 1} ^ i (j))$$

Các bạn hãy giúp Kichirou tính ~S(n)~ (~1 \le n \le 10^{12}~).

Một số tính chất của phép chia dư:

• ~(a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m~
• ~(a - b) \mod m = [(a \mod m) - (b \mod m)] \mod m~
• ~(a \cdot b) \mod m = [(a \mod m) \cdot (b \mod m)] \mod m~

Input

• Dòng duy nhất chứa một số nguyên dương ~n~ ~(1 \le n \le 10^{12})~.

Output

• In ra kết quả sau khi chia cho dư ~10^9 + 7~.

Samples

Sample Input

25

Sample Output

2925

Scores

• Subtask ~1~ (~40\%~ số điểm): ~1 \le n \le 10^3~.
• Subtask ~2~ (~40\%~ số điểm): ~1 \le n \le 10^6~.
• Subtask ~3~ (~20\%~ số điểm): ~1 \le n \le 10^{12}~.