Cho dãy số \(f_1, f_2, f_3, f_4, f_5, \dots\) được định nghĩa như sau:

• \(f_1 = 2\)
• \(f_i = f_{i-1} + i \cdot (i + 1)\)

Yêu cầu: Tính \(f_n\).

Input

• Một dòng duy nhất gồm số nguyên dương \(n\) (\(n \leq 10^9\)).

Output

• Một dòng duy nhất là giá trị của \(f_n\) sau khi chia lấy dư cho \(10^9 + 7\).

Example

4

40

Scoring

• \(40\%\) số điểm có \(n \leq 10^3\).
• \(40\%\) số điểm có \(n \leq 10^6\).
• \(20\%\) số điểm còn lại không có ràng buộc gì thêm.