Description

某Pell数列$a_1, a_2, a_3, \ldots,a_{n-1}, a_n$的定义如下：
$a_1=1, a_2=2, a_3=3, \ldots, a_n=a_{n-3}+2a_{n-2}+a_{n-1} (3<n<=35)。$

Format

Input

请输入一个正整数n

Output

第一行输出Pell数列中$a_n$项的值。
若采用递归方式处理，请计算递归调用总次数，并在第二行输出。

Samples

4

8
4

Limitation

1s, 1024KiB for each test case.