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 \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\).

Example

3

8

4

40