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))$ $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 \leq n \leq 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 - 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$ $(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 \leq n \leq 10^{12})$ .

Output

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

Samples

Sample Input

Copy

Sample Output

Copy

Scores

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

Comments

0

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

câu này lam sao mn

Link