Cho số nguyên dương \(n\). Đếm số hoán vị \((p_1, p_2, p_3, \dots, p_{2n})\) của \((1, 2, 3, \dots, 2n)\) sao cho tồn tại \(1 \le i \le 2n - 1\) thỏa mãn \(|p_i - p_{i+1}| = n\).

Input

• Gồm một số nguyên dương \(n\) (\(n \le 10^5\)).

Output

• In ra kết quả bài toán chia lấy dư cho \(10^9 + 7\).

Scoring

• Có \(10\%\) số điểm ứng với \(n \le 5\).
• Có \(90\%\) số điểm ứng với \(n \le 10^5\).

Example

2

16

5

2365440