问题描述

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

输入格式

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

输出格式

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

样例

输入 #1

2

输出 #1

4

输入 #2

8

输出 #2

68