Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CONNECTE - Connected Points

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


Được gửi lên bởi:sieunhan
Ngày:2009-05-14
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE
Nguồn bài:BOI

hide comments
2018-03-22 16:27:24
cho hoi n=5 ra bn






2018-03-22 16:08:48
cuu ae oi
2016-11-03 15:24:46
Code pascal:
http://shink.in/9iTHC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.