题目描述

这是语法课最后一个数列了，它满足

$a_1 = 0$

$a_2 = 1$

$a_3 = 1$

$a_4 = a_1 + 2 * a_2 + a_3$

$a_5 = a_2 + 2 * a_3 + a_4$

... ...

求 $a_n$。

输入格式

第一行输入整数 $n$。

输出格式

共一行，输出 $a_n$。

数据范围

$1 \leq n \leq 20$.

输入样例：

4

输出样例：

3