Xét một lưới đều gồm \(3 \times N\) điểm. Mỗi điểm có tối đa tám điểm kề như hình dưới đây.

Ta cần đếm số cách khác nhau để nối các điểm thành một đa giác thỏa mãn đồng thời:

1. Tập đỉnh của đa giác gồm toàn bộ \(3 \times N\) điểm.
2. Hai đỉnh liên tiếp của đa giác là hai điểm kề nhau trong lưới.
3. Đa giác đơn, tức là không tự cắt.

Hai đa giác có thể tạo được khi \(N=6\) được minh họa dưới đây.

Hãy tính số đa giác thỏa mãn theo modulo \(1\,000\,000\,000\).

Dữ liệu vào

Dòng duy nhất chứa một số nguyên dương \(N\).

Dữ liệu ra

In ra phần dư của số cách nối các điểm khi chia cho \(1\,000\,000\,000\).

Ràng buộc

Phân nhóm

• \(30\%\) số phép thử có \(N \le 200\).
• \(70\%\) số phép thử có \(N \le 100\,000\).

Ví dụ

3

8

4

40