三个同音连在一起

题目描述

长度 n 的每个位置写 A 或 B，求至少包含一段连续 AAA 的不同字符串数量。AAA 可以出现多次或相互重叠，但整条字符串只计一次。空串不包含 AAA。

输入格式

输入 n。

输出格式

输出数量。

样例 1

输入

3

输出

1

说明

只有 AAA。

样例 2

输入

2

输出

0

说明

长度不足三，不可能出现。

数据范围

• 0≤n≤50；答案使用 long long。