from bisect import bisect_left as bs

m = 10**9 + 7
m1 = m - 1
nmax = 10 ** 100
a = [0, 1, 2]
rs = {1}

r = 1
while True:
    if len(a) & 1:
        t = a[-1] * 2
        for v in a[1:]: rs.add(t - v)
        if a[-1] > nmax:
            break
    else:
        while r in rs: r+=1
        t = a[- 1] + r
        r += 1
        for v in a[1: -1]: rs.add(t - v)
    a.append(t)

rs = sorted(rs)
rp = [((a + 1) % m, b - a - 1) for a, b in zip(rs, rs[1:]) if a + 1 < b]

def go(seed, n, d):
    p2 = pow(2, n % m1, m)
    aa = seed + d + 1
    n %= m
    end = aa * p2 - d - n - 1
    ss = aa * (p2 - 1 <<1) - (d + 1) * n - ((n + 1) * n >> 1)
    return  end %m, ss % m



stamp = [0, 1]
info = [(0, 0, 0), (2, 2, 0)]
hm = nmax >> 1
u = 2
for l, c in rp:
    u, ts = go(u, c, l)
    stamp.append(stamp[-1] + c)
    info.append((u, (info[-1][1] + ts) % m, l))
    if stamp[-1] > hm: break

def sol(n):
    h = n >> 1
    k = bs(stamp, h)
    if h == stamp[k]:
        v = info[k]
    else:
        t = go(info[k - 1][0], h - stamp[k - 1], info[k][2])
        v = t[0], info[k - 1][1] + t[1]
    if n & 1:
        return (v[1] * 3 + 1)% m
    else:
        return (v[1] * 3 + 1 - v[0] * 2)% m


for _ in range(input()):
    print(sol(input()))