题目描述

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

输入

一个整数 $n$。

输出

第 $n$ 项的值。

样例

10

2378

来源

递推