Đường gấp khúc kỳ diệu
Xem dạng PDF
Gửi bài giải
Điểm:
0,94 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho lưới ~3 \times 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:
- Đường gấp khúc chứa tất cả ~3 \times N~ điểm của lưới.
- Chỉ các đỉnh kề nhau mới được nối với nhau
- Đường gấp khúc không tự cắt
Hình 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~.
Input
Dòng duy nhất chứa số nguyên ~N~ ~(3 \le N \le 1\,000\,000\,000)~.
Output
Gồm một dòng duy nhất là số cách nối theo mô đun ~1\,000\,000\,000~.
Sample Input 1
3
Sample Output 1
8
Sample Input 2
4
Sample Output 2
40
Bình luận
u