题目描述

佩尔数列满足 P1=0、P2=1，从第 3 项开始有 Pn=2P(n-1)+P(n-2)。求第 n 项。

输入格式

输入一个正整数 n（1 ≤ n ≤ 20）。

输出格式

输出佩尔数列的第 n 项。

输入样例 #1

7

输出样例 #1

70

输入样例 #2

1

输出样例 #2

0

输入样例 #3

2

输出样例 #3

1

数据范围

测试数据中，输入整数的取值范围为 1 至 20。