题目描述

有数列 $A_1​,A_2​,A_3​,A_4​,\dots,A_{20}​$。

已知：

$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​$，

$\dots$

$A_N​=A_{N-3}​​+2×A_{N−2​}+A_{N−1}​$，

求 $A_N​$。

输入格式

输入一行，包含一个整数 N 。

输出格式

输出一行，包含一个整数。

输入输出数据

输入数据 1

4

输出数据 1

3

数据范围

$1≤n≤20$。

记得给五星好评哦喵~ 谢谢客官啦~