hby与tkw的基情

题目背景

> 基情恒久远,一对永流传。 hby 和 tkw 是一对好基友,他们经常在一起做♂游♂戏 (/滑稽)。

题目描述

他们喜欢玩字符串游戏,尤其喜欢玩回文串。每次 hby 会给出一个数 $n$,那么 tkw 就需要给出 $Ans=\sum\limits_{i=1}^ni\times s[i]\times[i\bmod 2]$。其中 $s[i]$ 代表长度为 $i$ 的回文串的个数(只考虑小写字母),最后面是 bool 表达式 不过由于 tkw 最近学 ycz 找妹纸去了,于是他就将这个问题交给了你,如果你不能在 $1\rm s$ 内答出来,那么 hby 和 tkw 的基情将会破裂!~~(不过那样 tkw 就可以安心地找妹纸了)~~ 由于答案会非常大,所以你只需要输出答案 $\bmod 10^9+7$ 的值即可

输入输出格式

输入格式


第一行一个整数 $T$。 接下来 $T$ 行,每行一个数 $n$。

输出格式


共 $T$ 行,每行代表一个答案。

输入输出样例

输入样例 #1

2
1
3

输出样例 #1

26
2054

说明

对于 $10\%$的数据,$n\le 5$。 对于另外 $20\%$ 的数据,$\sum n\le 10^7$。 对于另外 $20\%$ 的数据,$T=1$。 对于 $100\%$ 的数据,$1\le T\le 5\times 10^5$,$1\le n\le 10^9$。