#NC22161. 牛牛学数列6

牛牛学数列6

题目描述

定义数列 {An}\{A_n\} 如下:

$$A_n=\begin{cases} 0,&n=1,\\ 1,&n\in\{2,3\},\\ A_{n-3}+2A_{n-2}+A_{n-1},&n\ge4. \end{cases}$$

给定正整数 nn,求 AnA_n 的值。

输入格式

在一行中输入一个整数 nn。当前离线题包的输入范围为 1≤n≤201\le n\le20。

输出格式

输出一个整数,表示 AnA_n 的值。

提示

A4=A1+2A2+A3=0+2×1+1=3A_4=A_1+2A_2+A_3=0+2\times1+1=3。

样例 1

4
3

来源

牛客原题