题目背景

基情恒久远，一对永流传。

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$ 行，每行代表一个答案。

2
1
3

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