Migrated from Lutece 1851 Alfa

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A good number is defined as all digits in decimal system are between $1$ and $9$, inclusive. The value of one good number can be calculate as follow:

Insert + into some of the positions (possibly none) between two digits.

After insertion, this good number can be evaluated as formulas, and the result is $S$.

The value is sum of $S$ of all possible legal insertion. The legal insertion is that any two neighbor digits can insert no more than one +. Inserting before the first digit or after the last digit is illegal.

Alfa wants you to calculate the value.

Input

The first line is an integer $T$($1 \leq T \leq 52$), which indicates the number of testcases.

For each testcase:

The one line of the input file contains a good number $N$($1 \leq |N| \leq 10^5$).

$|N| \leq 10^5$ means the length of N no more than $10^5$ and $N$ is positive integer.

Output

For each testcase, your program should output the value of the good number mod $10^9 + 7$.

Samples

1
157

250

1
315

378

Note

In the first example, the answer is calculated as follow:

157 = 157

1 + 57 = 58

15 + 7 = 22

1 + 5 + 7 = 13

157 + 58 + 22 + 13 = 250

Resources

The 16th UESTC Programming Contest Preliminary