Cho dãy số tứ diện: \(1, 4, 10, 20, 35, 56, \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.

Input

• Một số nguyên dương \(n\) duy nhất (\(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 số. Vì kết quả có thể rất lớn, hãy đưa ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).

Example

1

1

2

5

3

15

Constraints

• \(1 \le n \le 10^{12}\).