The Petrozavodsk camp takes place in about one month. Jafar wants to participate in the camp, but guess what? His coach is Yalalovichik.
Yalalovichik is a legendary coach, famous in the history of competitive programming. However, he is only willing to send to the camp students who solve really hard problems on Timus. The deadline that Yalalovichik set before has passed and he refuses to send Jafar to the camp.
Jafar decided to make Yalalovichik happy in hopes of changing his decision, so he invented a new sequence of numbers and named them Yalalovichik numbers. Jafar is writing a research paper about their properties and wants to publish it in the Science Eagle yearly journal.
A Yalalovichik number is created in the following way:
- Consider an integer $N$ in decimal notation; let's call it the base of the Yalalovichik number $Y_N$. $N$ may not contain the digit $0$.
- Treat $N$ as a decimal string. Compute all left shifts of this string $N_0, N_1, \ldots, N_{|N|-1}$ ($|N|$ denotes the number of digits of $N$); specifically, $N_k$ denotes the string formed by moving the first $k$ digits of $N$ to the end in the same order.
- Concatenate the strings $N_0, N_1, \ldots, N_{|N|-1}$. The resulting string is the decimal notation of $Y_N$.
For example, if $N = 123$, the left shifts are $123, 231, 312$ and thus $Y_N = 123231312$.
You are given the base $N$. Calculate the value of $Y_N$ modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single decimal integer $N$.

-----Output-----
For each test case, print a single line containing one integer — the value of the Yalalovichik number $Y_N$ modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 200$
- $|N| \le 10^5$
- $N$ does not contain the digit $0$
- the sum of $|N|$ over all test cases does not exceed $10^6$

-----Example Input-----
1
123

-----Example Output-----
123231312

```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 operator import mul\n\nM = 10 ** 9 + 7\nN = 100001\n\np10 = [None] * N\np10[0] = 1\nfor i in range(1, N):\n   p10[i] = p10[i - 1] * 10 % M \n\nt = int(input())\nfor _ in range(t):\n    s = list(map(int, input()))\n    m = p10[len(s)]\n    p = sum(map(mul, reversed(s), p10))\n    r = 0\n    for d in s:\n        r = (r * m + p) % M\n        p = (p * 10 - (m - 1) * d) % M\n    print(r)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 4013259