Nhiệm vụ của bạn là tính toán số dãy ngoặc hợp lệ có độ dài \(n\). Ví dụ: khi \(n = 6\), có \(5\) dãy:

• ()()()
• ()(())
• (())()
• ((()))
• (()())

Input

• Dòng đầu vào duy nhất có số nguyên \(n\) \((1 \leq n \leq 10^6)\)

Output

• In số lượng dãy chia lấy dư cho \(10^9 + 7\)

Example

6

5