Đường gấp khúc kỳ diệu

View as PDF

Submit solution

Points: 0.94 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
BOI
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho lưới ~3 \times N~ điểm. Mỗi điểm có tối đa 8 điểm xung quanh.

image

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

image

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.