题目描述

有数列A1​,A2​,A3​,A4​,…,A20​

已知

A1​=0

A2​=1

A3​=1

A4​=A1​+2×A2​＋A3​

A5​=A2​+2×A3​+A4​

……

AN​=AN-3​​+2×AN−2​+AN−1​

求 AN​

输入格式

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

输出格式

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

输入输出数据

4

3

数据范围

1≤n≤20。