Description

输出仅由0和1组成的长度为N的字符串，并且其中不可含有三个连续的相同子串。例如，110101就不含有三个连续的相同子串。而111010就含有一组长度为1的连续相同子串：111

Format

Input

第1行：字符串长度n（n≤40）

Output

第1行：1个整数，表示满足条件的字符串的个数。

Samples

2

4