Matcom Online Grader

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}$