The Bubble Cup hypothesis stood unsolved for $130$ years. Who ever proves the hypothesis will be regarded as one of the greatest mathematicians of our time! A famous mathematician Jerry Mao managed to reduce the hypothesis to this problem:

Given a number $m$, how many polynomials $P$ with coefficients in set ${\{0,1,2,3,4,5,6,7\}}$ have: $P(2)=m$?

Help Jerry Mao solve the long standing problem!


-----Input-----

The first line contains a single integer $t$ $(1 \leq t \leq 5\cdot 10^5)$ - number of test cases.

On next line there are $t$ numbers, $m_i$ $(1 \leq m_i \leq 10^{18})$ - meaning that in case $i$ you should solve for number $m_i$.


-----Output-----

For each test case $i$, print the answer on separate lines: number of polynomials $P$ as described in statement such that $P(2)=m_i$, modulo $10^9 + 7$.


-----Example-----
Input
2
2 4

Output
2
4



-----Note-----

In first case, for $m=2$, polynomials that satisfy the constraint are $x$ and $2$.

In second case, for $m=4$, polynomials that satisfy the constraint are $x^2$, $x + 2$, $2x$ and $4$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# ===============================================================================================\n# importing some useful libraries.\n\nfrom fractions import Fraction\nimport sys\nimport os\nfrom io import BytesIO, IOBase\nfrom itertools import *\nimport bisect\nfrom heapq import *\nfrom math import ceil, floor\nfrom copy import *\nfrom collections import deque, defaultdict\nfrom collections import Counter as counter  # Counter(list)  return a dict with {key: count}\nfrom itertools import combinations  # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]\nfrom itertools import permutations as permutate\nfrom bisect import bisect_left as bl\nfrom operator import *\n# If the element is already present in the list,\n\n# the left most position where element has to be inserted is returned.\nfrom bisect import bisect_right as br\nfrom bisect import bisect\n\n# If the element is already present in the list,\n# the right most position where element has to be inserted is returned\n\n# ==============================================================================================\n# fast I/O region\n\nBUFSIZE = 8192\nfrom sys import stderr\n\n\nclass FastIO(IOBase):\n    newlines = 0\n\n    def __init__(self, file):\n        self._fd = file.fileno()\n        self.buffer = BytesIO()\n        self.writable = "x" in file.mode or "r" not in file.mode\n        self.write = self.buffer.write if self.writable else None\n\n    def read(self):\n        while True:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            if not b:\n                break\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines = 0\n        return self.buffer.read()\n\n    def readline(self):\n        while self.newlines == 0:\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n            self.newlines = b.count(b"\\n") + (not b)\n            ptr = self.buffer.tell()\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\n        self.newlines -= 1\n        return self.buffer.readline()\n\n    def flush(self):\n        if self.writable:\n            os.write(self._fd, self.buffer.getvalue())\n            self.buffer.truncate(0), self.buffer.seek(0)\n\n\nclass IOWrapper(IOBase):\n    def __init__(self, file):\n        self.buffer = FastIO(file)\n        self.flush = self.buffer.flush\n        self.writable = self.buffer.writable\n        self.write = lambda s: self.buffer.write(s.encode("ascii"))\n        self.read = lambda: self.buffer.read().decode("ascii")\n        self.readline = lambda: self.buffer.readline().decode("ascii")\n\n\ndef print(*args, **kwargs):\n    """Prints the values to a stream, or to sys.stdout by default."""\n    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)\n    at_start = True\n    for x in args:\n        if not at_start:\n            file.write(sep)\n        file.write(str(x))\n        at_start = False\n    file.write(kwargs.pop("end", "\\n"))\n    if kwargs.pop("flush", False):\n        file.flush()\n\n\nif sys.version_info[0] < 3:\n    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)\nelse:\n    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\n\n# inp = lambda: sys.stdin.readline().rstrip("\\r\\n")\n\n# ===============================================================================================\n### START ITERATE RECURSION ###\nfrom types import GeneratorType\n\n\ndef iterative(f, stack=[]):\n    def wrapped_func(*args, **kwargs):\n        if stack: return f(*args, **kwargs)\n        to = f(*args, **kwargs)\n        while True:\n            if type(to) is GeneratorType:\n                stack.append(to)\n                to = next(to)\n                continue\n            stack.pop()\n            if not stack: break\n            to = stack[-1].send(to)\n        return to\n\n    return wrapped_func\n\n\n#### END ITERATE RECURSION ####\n\n# ===============================================================================================\n# some shortcuts\n\nmod = 1000000007\n\n\ndef inp(): return sys.stdin.readline().rstrip("\\r\\n")  # for fast input\n\n\ndef out(var): sys.stdout.write(str(var))  # for fast output, always take string\n\n\ndef lis(): return list(map(int, inp().split()))\n\n\ndef stringlis(): return list(map(str, inp().split()))\n\n\ndef sep(): return list(map(int, inp().split()))\n\n\ndef strsep(): return list(map(str, inp().split()))\n\n\ndef fsep(): return list(map(float, inp().split()))\n\n\ndef nextline(): out("\\n")  # as stdout.write always print sring.\n\n\ndef testcase(t):\n    for p in range(t):\n        solve()\n\n\ndef pow(x, y, p):\n    res = 1  # Initialize result\n    x = x % p  # Update x if it is more , than or equal to p\n    if (x == 0):\n        return 0\n    while (y > 0):\n        if ((y & 1) == 1):  # If y is odd, multiply, x with result\n            res = (res * x) % p\n\n        y = y >> 1  # y = y/2\n        x = (x * x) % p\n    return res\n\n\nfrom functools import reduce\n\n\ndef factors(n):\n    return set(reduce(list.__add__,\n                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))\n\n\ndef gcd(a, b):\n    if a == b: return a\n    while b > 0: a, b = b, a % b\n    return a\n\n\n# discrete binary search\n# minimise:\n# def search():\n#     l = 0\n#     r = 10 ** 15\n#\n#     for i in range(200):\n#         if isvalid(l):\n#             return l\n#         if l == r:\n#             return l\n#         m = (l + r) // 2\n#         if isvalid(m) and not isvalid(m - 1):\n#             return m\n#         if isvalid(m):\n#             r = m + 1\n#         else:\n#             l = m\n#     return m\n\n# maximise:\n# def search():\n#     l = 0\n#     r = 10 ** 15\n#\n#     for i in range(200):\n#         # print(l,r)\n#         if isvalid(r):\n#             return r\n#         if l == r:\n#             return l\n#         m = (l + r) // 2\n#         if isvalid(m) and not isvalid(m + 1):\n#             return m\n#         if isvalid(m):\n#             l = m\n#         else:\n#             r = m - 1\n#     return m\n\n\n##to find factorial and ncr\n# N=100000\n# mod = 10**9 +7\n# fac = [1, 1]\n# finv = [1, 1]\n# inv = [0, 1]\n#\n# for i in range(2, N + 1):\n#     fac.append((fac[-1] * i) % mod)\n#     inv.append(mod - (inv[mod % i] * (mod // i) % mod))\n#     finv.append(finv[-1] * inv[-1] % mod)\n#\n#\n# def comb(n, r):\n#     if n < r:\n#         return 0\n#     else:\n#         return fac[n] * (finv[r] * finv[n - r] % mod) % mod\n\n\n##############Find sum of product of subsets of size k in a array\n# ar=[0,1,2,3]\n# k=3\n# n=len(ar)-1\n# dp=[0]*(n+1)\n# dp[0]=1\n# for pos in range(1,n+1):\n#     dp[pos]=0\n#     l=max(1,k+pos-n-1)\n#     for j in range(min(pos,k),l-1,-1):\n#         dp[j]=dp[j]+ar[pos]*dp[j-1]\n# print(dp[k])\n\ndef prefix_sum(ar):  # [1,2,3,4]->[1,3,6,10]\n    return list(accumulate(ar))\n\n\ndef suffix_sum(ar):  # [1,2,3,4]->[10,9,7,4]\n    return list(accumulate(ar[::-1]))[::-1]\n\n\ndef N():\n    return int(inp())\n\n\n# =========================================================================================\nfrom collections import defaultdict\n\n\n\ndef numberOfSetBits(i):\n    i = i - ((i >> 1) & 0x55555555)\n    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)\n    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24\n\n\n\ndef solve():\n    n=N()\n    ar=lis()\n    for i in range(len(ar)):\n        m=ar[i]\n        v = m // 2\n        u = v // 2\n        w = (v - u)\n        print((u * w + u + w + 1) % mod)\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\nsolve()\n#testcase(int(inp()))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 194551