描述

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

输入

一个整数$n$。

输出

第$n$项的值。

样例

10

2378