a = [1, 2]
s = {1}
v = 1
K = 700
pre = [0]
for i in range(2, K) :
    if i % 2 == 0 :
        a.append(a[i - 1] * 2)
    else :
        while v in s :
            v += 1
        a.append(a[i - 1] + v)
        # print(v)
    for j in range(i) :
        s.add(a[i] - a[j])
P = 10 ** 9 + 7
pre = [0]
for i in range(K) :
    pre.append((pre[i] + a[i]) % P)
# print(a[len(a) - 1])
# print(10 ** 100)

s = list(s)
s.sort()
# print(s)

seg = []

for i in range(1, len(s)) :
    if s[i] > s[i - 1] + 1 :
        seg.append((s[i - 1] + 1, s[i]))

inv2 = pow(2, P - 2, P)

def calc(n) :
    return 2 * pow(inv2, n % (P - 1), P) * (P - n % P - 1 + pow(2, n % (P - 1), P)) % P

m = len(seg)
while seg[m - 1][0] > 10 ** 101 :
    seg.pop()
    m -= 1
pre1 = [0]
pre2 = [0]
cnt = [0]

for i in range(m) :
    (l, r) = seg[i]
    t = cnt[i]
    s1 = (r - l) * (l + r - 1) // 2 * (P - 3) % P
    s2 = calc(r - l) * pow(inv2, t % (P - 1), P) % P
    s2 = (s2 + l * 2 * (1 - pow(inv2, (r - l) % (P - 1), P) + P) * pow(inv2, t % (P - 1), P)) % P
    pre1.append((pre1[i] + s1) % P)
    pre2.append((pre2[i] + s2) % P)
    cnt.append(cnt[i] + r - l)

T = int(input())
for _ in range(T) :
    n = int(input())
    if n <= K :
        print(pre[n])
    else :
        v = (n - K) // 2
        s1 = pre[K]
        s2 = a[K - 1] * 4 % P
        s1 = (s1 + a[K - 1] * (P - 4)) % P
        if n % 2 == 1 :
            s2 = (s2 + a[K - 1] * 2) % P
        lo = 0
        hi = m - 1
        while lo < hi :
            x = (lo + hi + 1) // 2
            if cnt[x] <= v :
                lo = x;
            else :
                hi = x - 1
        s1 = (s1 + pre1[lo]) % P
        s2 = (s2 + pre2[lo] * (2 + n % 2)) % P
        t = cnt[lo]
        (l, r) = seg[lo]
        r = l + v - t
        s1 = (s1 + (r - l) * (l + r - 1) // 2 * (P - 3)) % P
        s2 = (s2 + calc(r - l) * pow(inv2, t, P) * (2 + n % 2)) % P
        s2 = (s2 + l * 2 * (1 - pow(inv2, r - l, P) + P) * pow(inv2, t, P) * (2 + n % 2)) % P
        ans = (s1 + s2 * pow(2, v, P)) % P
        print(ans)