线段树是小 $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$ 组数据的答案。

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