Đếm dãy nhị phân có độ dài n mà tồn tại 3 bit 1 đứng liên tiếp nhau.

Input Specification

• Một số nguyên dương duy nhất \(n\) \((0< n \le 20)\).

Output Specification

• In ra kết quả bài toán

Sample Input

4

Sample Output

3

Giải thích: các dãy thỏa mãn

0111
1110
1111