题目描述

输入一个整数 $n$ ，输出仅由 $0$ 和 $1$ 组成的长度为 $n$ 的字符串，并且其中不含有三个连续的相同子串。

仅需输出方案总数。

输入

一个整数，表示字符串长度 $n$ ($n \le 30$)。

输出

一个整数，表示所有满足条件的字符串的个数。

样例

2

4

8

68

来源

递归