Sherlock and Watson are playing a game. The game is as follows:

There are n cards in order on the table. Each card has some single digit number written on it. Sherlock asks Watson to form all ordered subsequences of the n cards and answer with the total of all the numbers obtained by each of the subsequence.

For example if cards are numbered as 1,2 and 3 in order. The subsequences obtained are: 1, 2, 3, 12, 13, 23, 123. Sum of the numbers of subsequence is = 1+2+3+12+13+23+123 = 177.

As the output can be large, output it modulo $10^9 + 7$

Watson is not so proficient at math and asks for your help.

Input

First line contains T : number of test cases. T lines follow, each containing a number having N digits. It is guaranteed that the first card will not have number 0 written on it.

Output

A number containing the sum of numbers obtained by each ordered subsequence.

Constraints

$1<= T <= 10$

$1<= N <= 2*10^5$ ( N is number of digits in given number)

Setter : Karan Thakkar