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, \dots\)

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 số nguyên dương \(n\).

Output

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

Example

5

11

Scoring

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