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\).

Output

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

Constraints

• \(1 \leq n \leq 10 ^ 6\)

Example

Sample input

6

Sample output

5