Cho trước số nguyên dương \(n\). Viết chương trình tính số dãy nhị phân độ dài \(n\) mà trong đó không chứa hai bit 0 ở cạnh nhau.

Input Specification

Gồm số nguyên dương \(n\) được ghi trên một dòng duy nhất.

Output Specification

In ra kết quả trên một dòng.

Constraints

\(n \leq 30\)

Input Sample

2

Output Sample

3

Explanation for Sample Output

Có ba dãy nhị phân thoả mãn là: 01, 10, 11.