The key is to stop looking at every term and instead look at the values used on the even steps.

The title is a hint: this is OEIS A001856, a classical self-generating difference sequence. (oeis.org)

Let

$$b_k = a_{2k}-a_{2k-1}.$$

Then every even step is “add $b_k$”, and every odd step is just doubling.

So the real problem is: how do we get the sequence $b_1,b_2,\dots$?

1. “Bad” differences and the $b_k$ blocks

Call a difference special if it is one of the adjacent even-step differences

$$a_{2k}-a_{2k-1}=b_k.$$

Put every other difference into a set fail.

Now fix some limit $L$. If we already built the original sequence until the last built term is even-indexed and bigger than $L$, then no future non-special difference $\le L$ can appear:

• a future odd term is $2x$, whose smallest new non-special difference is $x$;
• the next even term is $2x+b$, whose smallest new non-special difference is $x+b>x$.

So fail up to $L$ is final.

That means every number in $[1,L]$ that is not in fail will forever stay missing from the non-special differences, and the mex rule will pick them one by one as future $b_k$'s, in increasing order.

So between two consecutive fail values $f<g$, the $b_k$'s are simply

$$f+1,\ f+2,\ \dots,\ g-1.$$

That gives us long consecutive blocks.

2. Closed form inside one block

Suppose before a block starts, the current term is an odd-indexed term $x_0$, and the block is

$$s,\ s+1,\ \dots,\ s+m-1.$$

For the $t$-th pair in this block:

• even term: $x_t+s+t$
• next odd term:

$$x_{t+1}=2(x_t+s+t)=2x_t+2(s+t).$$

Define

$$y_t=x_t+2t+2s+2.$$

Then

$$y_{t+1}=2y_t,$$

so

$$x_t=2^t(x_0+2s+2)-2t-2s-2.$$

The sum added by $k$ full pairs is

$$\sum_{t=0}^{k-1}\bigl((x_t+s+t)+x_{t+1}\bigr) =3(x_0+2s+2)(2^k-1)-\frac{3k(k+2s+3)}2.$$

So a whole block, or any prefix of a block, is computable in $O(\log k)$ using pow(2, k, MOD).

3. How to build fail

We only need a finite prefix of the original sequence.

Build the original sequence directly from the statement:

• odd index: double;
• even index: add the smallest positive difference not seen yet.

While building, store all differences in a set diffs, and store all already-used special values $b_k$ in a set special.

Once the last built term is even and exceeds limit, all fail <= limit are final, so:

$$\text{fail} = (\text{diffs} \cap [1,\text{limit}]) \setminus \text{special}.$$

4. Complexity

If limit is around the largest query, the built prefix length is only $O(\log \text{limit})$, because every two steps the sequence more than doubles.

So:

• building the prefix and all its differences: $O(m^2)$, where $m=O(\log \text{limit})$;
• answering queries after sorting: $O(\#fail + T\log \text{limit})$.

This is easily fast enough in Python 3.12.

---

python
import sys

MOD = 1_000_000_007
INV2 = (MOD + 1) // 2


def build_fail(limit: int):
    """
    Build all 'fail' values in [1, limit].

    fail = all realized differences except the special adjacent ones
           a_{2k} - a_{2k-1}.

    We stop when the last built term is even-indexed and > limit.
    Then no future fail value <= limit can appear.
    """
    a = [1, 2]
    diffs = {0, 1}      # all differences already present in the built prefix
    special = {1}       # used values b_k = a_{2k} - a_{2k-1}
    mex = 0

    while len(a) % 2 == 1 or a[-1] <= limit:
        n = len(a) + 1

        if n & 1:  # odd index
            new = a[-1] * 2
        else:      # even index
            while mex in diffs:
                mex += 1
            new = a[-1] + mex
            special.add(mex)

        for old in a:
            diffs.add(new - old)
        a.append(new)

    fail = [x for x in diffs if 0 < x <= limit and x not in special]
    fail.sort()

    # Sentinel 0 on the left, limit+1 on the right.
    # The last sentinel is enough because we only need good numbers <= limit.
    fail.insert(0, 0)
    fail.append(limit + 1)
    return fail


def advance(cur_mod: int, start_mod: int, k: int):
    """
    A block starts with consecutive increments:
        start, start+1, ..., start+k-1

    cur_mod: current odd-indexed term before this block, modulo MOD.

    Returns:
        new_cur_mod: odd-indexed term after k full pairs
        added_sum_mod: sum contributed by those 2*k terms
    """
    km = k % MOD
    p2 = pow(2, k, MOD)

    base = (cur_mod + 2 * start_mod + 2) % MOD

    # x_k = 2^k * (x_0 + 2s + 2) - 2k - 2s - 2
    new_cur = (p2 * base - 2 * km - 2 * start_mod - 2) % MOD

    # sum of k full pairs:
    # 3 * (x_0 + 2s + 2) * (2^k - 1) - 3 * k * (k + 2s + 3) / 2
    added = (
        3 * base * (p2 - 1)
        - 3 * km * ((km + 2 * start_mod + 3) % MOD) * INV2
    ) % MOD

    return new_cur, added


def solve(queries):
    max_n = max(queries)

    # Usually one round is enough, but make it robust.
    limit = max_n
    while True:
        fail = build_fail(limit)

        fail_count = len(fail) - 2          # exclude 0 and sentinel
        good_count = limit - fail_count     # good numbers in [1, limit]
        covered_terms = 1 + 2 * good_count  # a1 + two terms per good number

        if covered_terms >= max_n:
            break
        limit *= 2

    order = sorted(range(len(queries)), key=queries.__getitem__)
    ans = [0] * len(queries)

    pos = 1       # first 'pos' terms are already accounted for
    cur = 1       # a_pos, and pos is always odd here
    pref = 1      # sum of first pos terms modulo MOD
    qi = 0

    for i in range(1, len(fail)):
        block_len = fail[i] - fail[i - 1] - 1
        if block_len <= 0:
            continue

        start = fail[i - 1] + 1
        block_end_pos = pos + 2 * block_len
        start_mod = start % MOD

        # Answer queries lying inside this block.
        while qi < len(order) and queries[order[qi]] <= block_end_pos:
            n = queries[order[qi]]
            delta = n - pos
            k = delta // 2

            cur_k, add_k = advance(cur, start_mod, k)
            res = (pref + add_k) % MOD

            if delta & 1:
                # One extra even-indexed term:
                # x_k + (start + k)
                extra = (cur_k + start_mod + (k % MOD)) % MOD
                res = (res + extra) % MOD

            ans[order[qi]] = res
            qi += 1

        if qi == len(order):
            break

        # Consume the whole block.
        cur, add_full = advance(cur, start_mod, block_len)
        pref = (pref + add_full) % MOD
        pos = block_end_pos

    return ans


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    queries = [int(x) for x in data[1:1 + t]]
    out = solve(queries)
    sys.stdout.write("\n".join(map(str, out)))


if __name__ == "__main__":
    main()

This matches the sample output and is fast enough for the full constraints.