English

Vietnamese

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/connecte

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:

• Đường gấp khúc chứa tất cả 3 × 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

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.

Input

Dòng duy nhất chứa số nguyên N (N <= 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.

Example

Input:
3

Output:
8

Input:
4

Output:
40