Cho lưới 3 × N điểm. Mỗi điểm có tối đa 8 điểm xung quanh.
Người ta nối các điểm của lưới tạo thành một đường gấp khúc khép kín với các tính chất sau:
Figure 2: Ví dụ 2 cách nối với N = 6.
Hãy viết chương trình tính số cách nối thỏa mã các điều kiện trên. Chú ý in ra kết quả theo mô đun 1,000,000,000.
Dòng duy nhất chứa số nguyên N (N <= 1,000,000,000).
Gồm một dòng duy nhất là số cách nối theo mô đun 1,000,000,000.