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

Nhập vào số nguyên dương \(n\). Hãy tìm số hạng thứ \(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à số hạng thứ \(n\) của dãy sau khi chia lấy dư cho \(10^9 + 7\).

Example

1

2

3

10

5

26