题目描述

小婷正在为珅泽教育的编程训练整理“Pell数列”任务，小泽负责把实际要求准确转换成程序。每一组输入都代表一次独立任务，程序必须严格遵守下面给出的规则，并按指定格式给出结果。

在核对方案时，他们发现即使任务看起来不长，边界情况、处理顺序和输出格式也同样重要。请认真阅读完整条件，帮助小泽完成这次训练。

Pell数列的定义是这样的，a1=1， a2=2,...,

a_n=2a_n−1+a_n−2(n>2)。

给出一个正整数k，要求Pell数列的第k项是多少(结果对1e9+7取模)。

输入格式

输出格式

输入样例 #1

2
1
8

输出样例 #1

1
408

输入样例 #2

2
8
1

输出样例 #2

408
1

输入样例 #3

4
1
9
2
8

输出样例 #3

1
985
2
408

数据范围

an=2an−1+an−2(n>2)。

每组测试数据占1行，包括一个正整数k (1≤k<1000000)。