Cho dãy số có quy luật như sau: \(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...\)

Yêu cầu: Cho số nguyên dương \(n\), hãy tính tổng \(n\) số đầu tiên của dãy.

Input

• Gồm một dòng chứa một số nguyên dương \(n\).

Output

• In ra một số nguyên là tổng \(n\) số đầu tiên của dãy chia dư cho \(10^9 + 7\).

Scoring

• Subtask #1 (\(50\%\) số điểm): \(n \leq 10^6\)
• Subtask #2 (\(50\%\) số điểm): \(n \leq 10^{18}\)

Example

5

11