Dãy đèn tiết kiệm - Đếm số cách hợp lệ

Trên một hàng rào có n bóng đèn xếp thành một hàng. Mỗi bóng đèn có một trong hai trạng thái: tắt (kí hiệu 0) hoặc bật (kí hiệu 1). Mỗi cách bật/tắt được biểu diễn bởi một xâu gồm n kí tự 0 và 1.

Để tiết kiệm điện, không được có hai bóng đèn liền kề cùng bật, tức là trong xâu không được xuất hiện hai kí tự 1 đứng cạnh nhau. Một cách bật/tắt thỏa quy định này được gọi là cách hợp lệ.

Ví dụ, với n = 3 có đúng 5 cách hợp lệ: 000, 001, 010, 100, 101.

Yêu cầu

Hãy đếm số cách bật/tắt hợp lệ. Chương trình phải sử dụng hàm đệ quy.

Input

Một dòng duy nhất chứa số nguyên n.

Output

In một số nguyên là số cách bật/tắt hợp lệ.

Ràng buộc

• 1 ≤ n ≤ 25.

Ví dụ 1

Input

4

Output

8

Ví dụ 2

Input

20

Output

17711