Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito es amante de los palíndromos, palabras que se leen igual del derecho que al revés. Él ya está cansado de ver ejemplos de palíndromos ($\texttt{aba}$, $\texttt{hggh}$, $\texttt{a}$,…), actualmente está más interesado en contarlos. El desea saber cuántos palíndromos hay de tamaño menor igual que $N$ usando solo caracteres en minúscula del alfabeto en inglés $(\texttt{a}, \texttt{b}, ..., \texttt{z})$.

Input

La primera línea representa la cantidad de casos $T$ $(1 \leq T \leq 1000)$. Siguen $T$ líneas cada una con un entero $N$ $(1 \leq N \leq 10^9)$.

Output

La salida contiene la cantidad de palíndromos de longitud a lo sumo $N$ por cada caso de prueba, modulo $1000000007$.

Sample test(s)

Hints

Primer caso ($N = 2$)
$\texttt{a}, \texttt{b}, ..., \texttt{z}$
$\texttt{aa}, \texttt{bb}, ..., \texttt{zz}$