Phân Chia Miền Hình Tròn

Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256MB

Mô tả bài toán

Cho một vòng tròn và ~n~ điểm phân biệt nằm trên đường tròn đó. Tiến hành nối tất cả các cặp điểm với nhau bằng các dây cung. Giả sử vị trí của các điểm được chọn sao cho không có 3 dây cung nào đồng quy (cắt nhau tại cùng 1 điểm) ở phía trong hình tròn.

Hãy tính số lượng miền (vùng) nhỏ được chia ra bên trong hình tròn đó. Vì kết quả có thể rất lớn, hãy in ra kết quả sau khi lấy dư cho ~10^9 + 7~.

Mỗi hình tròn ban đầu tương ứng với 1 miền. Cứ thêm dây cung và các giao điểm, số lượng miền sẽ tăng lên như hình minh họa dưới đây:

Minh họa số miền tương ứng với n từ 1 đến 5

Dữ liệu vào (Input)

• Dòng đầu tiên chứa một số nguyên duy nhất ~n~ (~1 \le n \le 10^9~).

Dữ liệu ra (Output)

• In ra một số nguyên duy nhất là số miền tìm được sau khi lấy modulo ~10^9 + 7~.

Giới hạn & Chấm điểm (Constraints & Subtasks)

• Subtask 1 (30% số điểm): ~1 \le n \le 5~
• Subtask 2 (30% số điểm): ~1 \le n \le 1000~
• Subtask 3 (40% số điểm): ~1 \le n \le 10^9~

Ví dụ (Examples)

Input	Output	Hình minh họa
4	8
5	16
6	31

Giải thích (Explanation)

• Với ~n = 4~, vòng tròn được chia tối đa thành 8 miền.
• Với ~n = 5~, vòng tròn được chia tối đa thành 16 miền.
• Với ~n = 6~, vòng tròn được chia tối đa thành 31 miền (hãy cẩn thận, quy luật không phải là lũy thừa của 2).