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