Số Catalan thứ \(n\) được định nghĩa: \(C_n = \frac{1}{n+1} \times C_{2n}^n\). Tính \(C_n \bmod MOD\) với \(MOD = 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à số Catalan thứ \(n\) modulo \(10^9+7\).

Ví dụ

Input:

3

Output:

5

Giải thích: Dãy Catalan: 1, 1, 2, 5, 14, ... Số thứ 3 là 5.

Ràng buộc

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