Background

Bromance lasts forever, a pair will be passed down for eternity.

hby and tkw are a pair of close buddies. They often play “games” together (/joking).

Problem Description

They like playing string games, and they especially like palindromes. Each time, hby gives a number $n$, and then tkw needs to give $Ans=\sum\limits_{i=1}^ni\times s[i]\times[i\bmod 2]$. Here, $s[i]$ represents the number of palindromic strings of length $i$ (only lowercase letters are considered). The last part is a bool expression.

However, recently tkw has been learning from ycz to go find a girlfriend, so he handed this problem to you. If you cannot answer it within $1\rm s$, then the bromance between hby and tkw will break! (But then tkw can focus on finding a girlfriend.)

Since the answer will be very large, you only need to output the value of the answer $\bmod 10^9+7$.

Input Format

The first line contains an integer $T$.

In the next $T$ lines, each line contains one number $n$.

Output Format

There are $T$ lines in total, each line represents one answer.

2
1
3

26
2054

Hint

For $10\%$ of the testdata, $n\le 5$.

For another $20\%$ of the testdata, $\sum n\le 10^7$.

For another $20\%$ of the testdata, $T=1$.

For $100\%$ of the testdata, $1\le T\le 5\times 10^5$, $1\le n\le 10^9$.

Translated by ChatGPT 5