1435 - 【入门】数列求值3

1435 - 【入门】数列求值3

通过次数

29

提交次数

70

旧版界面

Time Limit : 1 秒

Memory Limit : 128 MB

数列 $A_1,A_2,A_3,A_4,\dots$ , $A_9$ 已知

$A_1$ =0
$A_2$ =1
$A_3$ =1
$A_4$ = $A_1+2A_2＋A_3$
$A_5$ = $A_2+2A_3+A_4$

求 $A_n$

Input

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

Output

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

Examples

Input

Output

Hint

1<=n<=28