Cho dãy số: \(2, 5, 10, 17, 26, \dots\)

Nhập vào số nguyên dương \(n\). Hãy tính tổng của \(n\) số hạng đầu tiên của dãy số trên.

Input

• Một dòng duy nhất chứa số nguyên dương \(n\) (\(1 \le n \le 10^{12}\)).

Output

• Một số nguyên duy nhất là tổng của \(n\) số hạng đầu tiên của dãy sau khi chia lấy dư cho \(10^9 + 7\).

Example

3

17

5

60