P4881 hby and tkw’s Bromance

> 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).

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

The first line contains an integer $T$. In the next $T$ lines, each line contains one number $n$.

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

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