Cho số nguyên dương \(n\), đếm số cách chia các số từ \(1\) đến \(2n\) thành \(n\) nhóm, mỗi nhóm gồm hai số mà hiệu hai số trong một nhóm bằng hiệu hai số trong nhóm khác.

Input

• Gồm nhiều dòng, mỗi dòng gồm một số \(n\) (\(n \le 10^6\)), có không quá \(10^6\) dòng.

Output

• Gồm nhiều dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.

Example

1

1

2

2