题目内容

对于一个长度为$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$