2860. Pell数列

【题目描述】

Pell数列是这样一个数列，它的前两项$a_1=1，a_2=2$，通项的定义是$a_n=2*a_{n - 1}+a_{n-2}（n>2）$。

给定一个正整数$n$，求$Pell$数列的第$n$项对$10^9+7$取余的结果。

【输入格式】

第一行一个整数$q$。

接下来$q$行，每行一个整数$n$，表示要求Pell数列的第$n$项。

【输出格式】

输出共$q$行，每行一个整数表示询问的第$n$项对$10^9+7$取余的结果。

【样例输入】

2
3
8

【样例输出】

5
408

【数据规模与约定】

对于10%的数据，$n\leq 25$；

对于20%的数据，$n\leq 50$；

对于60%的数据，$n\leq 10^6,q\leq 100$；

对于100%的数据，$n\leq 10^6,q\leq 10^4$。