P14111 [ZJCPC 2017] Chiaki Sequence

Chiaki 对一个无限数列 $a_1,a_2,a_3,\dots$ 感兴趣，该数列定义如下： $$a_n = \begin{cases} n & n \le 2 \\ 2 \cdot a_{n-1} & n \text{ 为奇数} \\ a_{n-1} + r_{n-1} & n \text{ 为偶数} \end{cases}$$ 其中 $r_n$ 是满足 $S_n = \{a_j - a_i \mid 1 \le i < j \le n\}$ 的集合中没有出现的最小正整数。 Chiaki 想知道该数列的前 $n$ 项和，即 $\sum\limits_{i=1}^{n} a_i$。由于这个数可能非常大，Chiaki 只关心它对 $10^9+7$ 取模后的结果。

有多组测试用例。输入的第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的数量。对于每组测试用例： 第一行包含一个整数 $n$（$1 \le n < 10^{100}$），无前导零。

对于每组测试用例，输出一个整数表示答案。

由 ChatGPT 5 翻译