Cho dãy số: \(5, 12, 21, 32, 45, \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

5

2

12

3

21