题目描述

定义数列 $F$： $ F(x) = \begin{cases} 1; & x \le 3 \\ F(x-1) + 2 \times F(x-3). & \text{otherwise} \end{cases} $ 先请你编写一个程序，使其能够在规定时间内输出 $F$ 的第 $n$ 项。

输入描述

输入仅一行，一个正整数 $n$ 。

输出描述

输出仅一行，一个正整数，$F(n)$。 答案可能会超过 $2^{31}-1$ ，请使用 64 位整型存储。

5

5

约定

$1 \le n \le 40$