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

LATGACH2 - Lát gạch 2

Trước tiên các bạn cần xem bài LATGACH ( level 1 ).
Xét một hình vuông kích thước (n+2)x(n+2) (3<=n<=1000). Hình vuông này bị khuyết mất một diện tích là hình vuông kích thước (n-2)x(n-2) ở trung tâm ( Như vậy chỉ còn 4 đường biên với độ rộng là 2 ). Bạn vẫn được quyền sử dụng các viên gạch kích thước 1x2 và 2x1 để lát vừa kín hình trên. Hãy đếm số cách lát.

Input

Gồm nhiều dòng, mỗi dòng ghi 1 số n của test tương ứng.

Output

Với mỗi số n trong input, bạn cần đưa ra một số tương ứng ở output thể hiện số cách lát.

Example

Input:
3
50

Output:
196
401520777816387690468975409805843797460004

Được gửi lên bởi:VOJ problem setters
Ngày:2008-01-17
Thời gian chạy:0.637s
Giới hạn mã nguồn:7000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Mở rộng của bài lát gạch

hide comments
2017-06-15 17:29:07
Thế là phải dùng số lớn hả các bác =(
2016-10-16 10:28:44
http://plouffe.fr/OEISrational_fractions/220/A220436.txt
2015-06-16 17:10:50 Phong


Last edit: 2017-01-01 16:59:12
2015-05-21 14:32:11 Sue
đề chơi ác thế :v
công thức là 2(f(n-2)+f(n+2)) với f(n) là số fibonacci thứ n
c/minh: dễ dàng theo bài LATGACH và vẽ hình ta có đpcm :3

Last edit: 2015-05-21 14:34:40
2014-08-24 10:24:28 [CHV] Bác Thợ Sãn
ai biết công thức bài này không chỉ em với
2014-08-06 18:15:31 Lâm Thành Ðạt
n=300 kết quả đã hơn 300 kí tự rồi @@
2014-08-04 15:19:53 Crocodile
làm đúng rồi mà bị chạy lâu mới nản @@ . Ai biết cách fix ko
2011-05-21 19:15:29 dhkhtn
n = 1000:

571137891500108315332304959588980983603425473903887536410792.........

Last edit: 2011-05-21 19:16:21
2010-01-19 14:05:04 Nguyễn Trung Hiếu
vậy là biên fải có độ rộng = 4 chứ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.