牛牛学数列6
题号：NC22161
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}定义数列 \{A_n\} 如下：

\displaystyle A_n=<br />\begin{cases}<br />0,& n\in\{1\};\\<br />1,& n\in\{2,3\};\\<br />\displaystyle A_n = A_{n-3} + 2A_{n-2} + A_{n-1},& n \geqq 4.<br />\end{cases}

\hspace{15pt}给定正整数 n，求 A_n 的值。

输入描述:

\hspace{15pt}在一行中输入一个整数 n，满足 1 \leqq n \leqq 20。

输出描述:

\hspace{15pt}输出一个整数，表示 A_n 的值。
示例1

输入

复制 
4

输出

复制 
3

说明

A_4 = A_1 + 2A_2 + A_3 = 0 + 2\times1 + 1 = 3。