NQOJ
Đăng nhập Đăng ký
Ngôn ngữ

Điều hướng chính

Ngôn ngữ

Phím tắt

/
Chuyển đến ô tìm bài
g p
Đi đến bài tập
g c
Đi đến kỳ thi
g u
Đi đến người dùng
?
Mở trợ giúp phím tắt

Mật mã lỏng lẻo

Dễ

  • 100 Điểm
  • 100% Tỉ lệ AC
  • 1 Số AC
  • 256M Bộ nhớ giới hạn
  • 1.0s Giới hạn thời gian

Thám tử K cho phép chuỗi nhị phân có cặp \(00\) xuất hiện, nhưng chỉ không quá 2 lần. Hãy sử dụng đệ quy để liệt kê tất cả các chuỗi nhị phân có độ dài \(N\) thỏa mãn ràng buộc về số lần xuất hiện của cặp "00".

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 15\)).

Output

In ra số lượng chuỗi nhị phân thỏa mãn điều kiện.

Example

Test 1

Input 
1
Output 
2

Test 2

Input 
2
Output 
4

Test 3

Input 
3
Output 
8

Test 4

Input 
4
Output 
15
0 Thích
Báo cáo

Bình luận

Chưa có bình luận nào.