Số Catalan thứ \(n\): \(C_n = \frac{1}{n+1} \times C_{2n}^n\). Tính \(C_n \bmod (10^9+7)\).

Định dạng đầu vào

• Một dòng chứa số nguyên \(n\) (\(0 \le n \le 10^6\)).

Định dạng đầu ra

• Một số nguyên là \(C_n \bmod (10^9+7)\).

Ví dụ

Input:

3

Output:

5

Ràng buộc

• 100% số điểm: \(n \le 10^6\).