题目描述

《Pell数列》

【Pell数列】 有一种数列，它的前 10 项的值分别为： 1 2 5 12 29 70 169 408 985 2378 ，这个数列被称为 Pell 数列，请问该数列的第 n 项的值是多少？（ 0<n<=1000 ） 公式：Pell[1] = 1, Pell[2] = 2, Pell[n] = 2*Pell[n-1] + Pell[n-2] （n>2）

输入格式

一个整数 n

输出格式

第 n 项的值

样例

输入样例 1

10

输出样例 1

2378

输入样例 2

20

输出样例 2

15994428

输入样例 3

25

输出样例 3

1311738121

输入样例 4

100

输出样例 4

66992092050551637663438906713182313772