U405701 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$取余的结果。

对于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$。