Pell数列

题目描述:

$Pell$数列 $a_1,a_2,a_3,\dots$ 的定义是这样的，$a_1=1,a_2=2,\dots ,a_n=2a_{n-1}+a_{n-2}(2<n)$  

给出一个正整数 $k$，要求 $Pell$ 数列的第$k$ 项模上$32767$ 是多少。

输入格式:

一个正整数 $k(1\le k<1,000,000)$ 

输出格式:

一个非负整数。

样例输入:

8

样例输出:

408

时间限制: 1000ms
空间限制: 256MB

---

来源: 原创