题目描述

定义双前项倍乘数列 F(n):

初始条件:F(1)=1,F(2)=2

递推关系:当 n≥3 时,F(n)=F(n−1)×2+F(n−2)×3

给定正整数 n,请使用一重循环递推计算并输出 F(n) 的值。

输入

输入一个正整数 n(满足 1≤n≤30)

输出

输出一行,包含一个整数,表示 F(n) 的值。

样例

样例 1

输入

3

输出

7
样例 2

输入

4

输出

20