思路:OEIS大法

1.组合数学分析做法不太会

2.考虑暴力求n = 1 , 2 ,3 , 4 , 5 的结果为:1,8 , 40,160,560

3.将序列丢入oeis (存储所有数列通项公式的数据库), 可以得到结果:$C_{n+2}^{3} * 2^{n-1}$

4.第一次接触取模操作的uu可以看看这篇文章

题目内容

对于一个长度为$k$且只包含字符$0$和$1$的字符串$s_1s_2...s_k$，定义其权值为:

• 每次操作可以选择一个下标$i(1≤i≤k)$，将$[1,i]$的字符全部取反($0$变$1$，$1$变$0$);

• 将字符串变为全$1$需要的最少操作次数。

例如字符串$00110$，

第一次操作选择$i=5$，字符串变成$11001$；

第二次操作选择$i=4$，字符串变成$00111$；

第三次操作选择$i=2$，字符串变成$11111$；

至少需要$3$次操作，字符串权值为$3$。

定义其重量为:该字符串的全部非空子串的权值总和。

子串是指从原字符串中，连续的选择一段字符组成的新字符串。

现在，给出一个整数$n$，问:全部长度为$n$的$0-1$的字符串的重量总和是多少?

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数$T(1≤T≤10^3)$代表数据组数，每组测试数据描述如下：

每行输入一个整数$n(1≤n≤10^6)$表示给定的整数。

除此之外，保证所有的$n$之和不超过$10^7$。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表重量总和。

由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

示例1

输入

2
2
1

输出

8
1

说明

对于第一组测试数据，全部$0-1$子串有$00,01,10,11$