题目描述

有一种数列，它的前 $10$ 项的值分别为：$1, 2, 5, 12, 29, 70, 169, 408, 985, 2378$，这个数列被称为 Pell 数列。请问该数列的第 $n$ 项的值是多少？

输入格式

输入一个正整数 $n$。

输出格式

输出第 $n$ 项的值。

样例

10

2378

数据范围与提示

$n \le 1000$

来源

递推