A29907.小坤的数列【递归】

给定一个数列 $F$ 定义如下：

• 递推关系：
  $F(x) = \begin{cases} F(x-1) + 2 \times F(x-3), & x > 3 \\ 1, & x \leq 3 \end{cases}$
• 任务：编写一个程序，在合理的时间复杂度内计算并输出 $F(n)$ 的值。

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

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

数据范围

• $1≤n≤40$