Lát gạch 2

View as PDF

Submit solution


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

Problem source:
Mở rộng của bài lát gạch
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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)~ ~\times~ ~(n + 2)~ ~(3 \le n \le~ ~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) \times (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 ~1 \times~ ~2~ và ~2 \times~ ~1~ để 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.

Sample Input

3
50

Sample Output

196
401520777816387690468975409805843797460004

Comments

Please read the guidelines before commenting.


There are no comments at the moment.