题目描述

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

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

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

小 L 定义了一个函数 $cover(a, b)$（$1 \le a \le b \le 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 \le T \le 1000$）表示数据组数。
接下来 $T$ 行，其中第 $i$（$1 \le i \le T$）行一个正整数 $n$（$1 \le n \le {10}^{18}$）表示第 $i$ 组数据。

输出格式

$T$ 行，第 $i$（$1 \le i \le 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}$。

来源

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。