题目描述

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

a1 = 0

a2 = 1

a3 = 1

a4 = a1 + 2 * a2 + a3

a5 = a2 + 2 * a3 + a4

... ...

求 an

输入格式

第一行输入整数 n；

输出格式

共一行，输出 an;

数据范围

1 <= n <= 20

输入样例：

4

输出样例：

3