题目描述

编写一个程序，计算满足如下递推关系的数列第n项： $$ F(n)= \begin{cases} 1, & n=0 \ 3, & n=1 \ 4*F(n-1)-F(n-2), & n>1 \end{cases} $$

输入描述

用户输入整数 $n$（$0 \leq n < 10$）。

输出描述

输出一个整数，即第 $n$ 个元素的值。

输入样例1

5

输出样例1

571

样例1解释

递推计算过程如下：

• F(0) = 1
• F(1) = 3
• F(2) = 4F(1) - F(0) = 43 - 1 = 11
• F(3) = 4F(2) - F(1) = 411 - 3 = 41
• F(4) = 4F(3) - F(2) = 441 - 11 = 153
• F(5) = 4F(4) - F(3) = 4153 - 41 = 571