线段树是小 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}。