Số Catalan thứ N
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề bài
Số Catalan thứ $n$ được định nghĩa bởi $C_0 = 1$ và $C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}$ với $n \ge 1$. Hãy viết hàm đệ quy có nhớ để tính $C_N \bmod (10^9 + 7)$.
Dữ liệu vào
Một dòng duy nhất chứa số nguyên không âm $N$.
Dữ liệu ra
Một số nguyên duy nhất là giá trị $C_N \bmod (10^9 + 7)$.
Ví dụ
| Input | Output |
|---|---|
| 3 | 5 |
| 4 | 14 |
Giới hạn
$0 \le N \le 500$.
Community Discussion