A number K$K$ is said to be magical if it can be represented as a power of 2 only.That is K$K$=2x$2^{x}$ for some natural number x$x$. 
Given a string of digits S$S$ of length N$N$, Let P be a valid arrangement of S.
By valid arrangement we mean that it should not have any leading zeroes.
Find the sum of all such distinct Pi's, which, when treated as a number is magical.
Two arrangements are said to be distinct, if there is atleast one index where they differ. 
As the sum can be very large, print the sum modulo 109+7$10^{9}+7$.

-----Input:-----
-The first line of the input contains a single integer T$T$ denoting the number of test cases. 
-Only line of each test case contains a string S$S$ of length N$N$, consisting only of digits between 0 to 9.

-----Output:-----
For each test case, print a single integer denoting the sum of all such magical Pi′s$Pi's$ modulo 109+7$10^{9}+7$.
If no such Pi$Pi$ exists print "-1".

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 2≤N≤1000$2 \leq N \leq 1000$
- String only consists of digits between 0 to 9, both inclusive.

-----Subtasks-----
- 10 points : 1≤N≤5$1 \leq N \leq 5$
- 40 points : 1≤N≤100$1 \leq N \leq 100$
- 50 points : Original Constraints

-----Sample Input:-----
2
35566

31

-----Sample Output:-----
65536

-1

-----EXPLANATION:-----
Only arrangement is 65536.
No arrangement of 31 gives us a power of two.

```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 = "from math import log,floor\n\nt = int(input())\n\nwhile(t>0):\n\tn = str(input())\n\tn1 = int(''.join(sorted(n)))\n\tn2 = int(''.join(sorted(n, reverse=True)))\n\tlow = pow(2,floor(log(n1,2)))\n\thigh = pow(2,floor(log(n2,2)))\n\n\ti = low\n\tans = 0\n\twhile(i<=high):\n\n\t\t# print(i)\n\t\tk = str(i)\n\t\tk = ''.join(sorted(k))\n\t\tif i>= n1 and int(k) == n1:\n\t\t\tans += i\n\t\t\t\n\n\t\ti = i<<1\n\n\n\tmod = 1000000007\n\tif ans != 0:\n\t\tprint(ans%mod)\n\telse:\n\t\tprint(-1)\n\n\tt-=1\n\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13409