问题描述

线段树是小$L$最喜欢的数据结构，它能高效地解决许多实际问题。

给定一个正整数$n$，小$L$构建出一棵下标属于整数区间$[1,n]$的线段树：

• 初始线段树只有一个结点$[1,n]$。
• 对于结点$[L,R]$，若$L<R$，则令$mid=[\frac{L+R}{2}]$（$[x]$表示不超过$x$的最大整数），小$L$对这个结点建出两个子结点$[L,mid]$、$[mid+1,R]$。

小$L$定义了一个函数$cover(a,b)(1\leq a\leq b\leq n)$，表示用若干个线段树结点不重不漏地覆盖区间$[a,b]$，则使用的线段树结点个数的最小值。

小$L$尝试使用这棵线段树解决某个复杂问题，并想要粗略地评估这棵线段树的性能。

具体来说，区间$[1,n]$有$\frac{n(n+1)}{2}$个不同的子区间，如果小$L$从这$\frac{n(n+1)}{2}$个子区间中等概率随机地选取一个，将其记为$[A,B]$，则小$L$认为$cover(A,B)$的期望值可用于评估此线段树的性能。

小$L$想请你帮他计算出$cover(A,B)$的期望值与$\frac{n(n+1)}{2}$的乘积对$1,000,000,007$取模的结果，可以发现此结果一定是一个整数。

输入格式

第一行一个正整数$T(1\leq T\leq 1000)$表示数据组数。

接下来$T$行，其中第$i(1\leq i\leq T)$行一个正整数$n(1\leq n\leq 10^{18})$表示第$i$组数据。

输出格式

$T$行，第$i(1\leq i\leq T)$行一个整数表示第$i$组数据的答案。

1
3

7

样例解释

$cover(1,1)=1$，$cover(2,2)=1$，$cover(3,3)=1$，$cover(1,2)=1$，$cover(2,3)=2$，$cover(1,3)=1$，故$cover(A,B)$的期望$=\frac{1+1+1+1+2+1}{6}=\frac{7}{6}$。