Subsequences
Tag(s):

Medium

Problem
Editorial
Analytics

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

SAMPLE INPUT
2
123
111
SAMPLE OUTPUT
177
147
Explanation

The subsequence of number 123 are 123, 12 , 23, 13, 1, 2 and 3. Whose sum is 177.

The subsequence of number 111 are 111, 11 , 11, 11, 1, 1 and 1. Whose sum is 147.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...