#1486. 【提高】Pell数列

【提高】Pell数列

说明

有一种数列,它的前8项的值分别为:1 2 5 12 29 70 169 408,这个数列被称为Pell数列,请问该数列的第n项的值是多少?(n<=1000

输入格式

一个整数n

输出格式

n项的值

样例

10
2378