问题描述

有数列 $A_1,A_2,A_3,A_4,…,A_{20}$

已知

$A_1=0$

$A_2=1$

$A_3=1$

$A_4=A_1+2 \times A_2＋A_3$

$A_5=A_2+2 \times A_3+A_4$

$\dots$

$A_n=A_{n-3}+2 \times A_{n-2} + A_{n-1}$

求 $A_n$

输入

输入一行，包含一个整数 $n$

输出

输出一行，包含一个整数 $A_n$

样例

4

3

数据范围

$1≤n≤20$