Con số bí ẩn

Time limit: 1.0s , Memory limit: 256M , Points: 20 (partial)

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)$ ~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$ ~1~ đến một số nguyên dương $n$ ~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$ ~10^9 + 7~. Công thức tính $S(n)$ ~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)$ ~S(n)~ ( $1 \le n \le 10^{12}$ ~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$ ~n~ $(1 \le n \le 10^{12})$ ~(1 \le n \le 10^{12})~.

Output

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

Samples

Sample Input

Sample Output

Scores

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

Comments

0

T-JUN-8507 commented on Dec. 21, 2024, 7:00 a.m.

câu này lam sao mn

Link