Số Catalan C_n đếm số cây nhị phân khác nhau có n nút, số cách đặt dấu ngoặc hợp lệ cho n cặp ngoặc, v.v. Tính C_n = comb(2n, n)/(n+1). Vì kết quả lớn, in ra theo modulo 10^9+7.
Một dòng chứa số nguyên n (0 ≤ n ≤ 100000).
0 ≤ n ≤ 100000.
Số Catalan thứ n lấy modulo 10^9+7.
Ví dụ:
Đầu vào:
3
Đầu ra:
5
Giải thích:
Đang tải editor...