Cho dãy số: \(1, 4, 10, 20, 35, 56, \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 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à số hạng thứ \(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

4

3

10

4

20

Note

Dãy số trên là dãy số tứ diện (Tetrahedral numbers), trong đó số hạng thứ \(n\) được tính bằng công thức: