2017 Asia HCMC Vietnam National Programming Contest

Start

2017-11-05 01:00 UTC

2017 Asia HCMC Vietnam National Programming Contest

End

2017-11-05 06:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -400 days 12:42:15

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Cumulative Sums

While learning mathematics at school, Hieu amazingly invented a new sequence of numbers. It can be defined as below:

\begin{align*} A_1 & = 1 \\ A_ i & = A_{i-1} + sod(A_{i-1}) \end{align*}

Here $sod(X)$ is the sum of digits of $X$ (in base $10$)

The first few elements of sequence $A$ is $[1,2,4,8,16,23,28,38,49,62,70,77,91,\ldots ]$. Hieu also researched on its cumulative sums. The cumulative sums $S$ of the sequence $A$ is defined as:

\begin{align*} S_ i=\sum \limits _{j=1}^ i A_ j \end{align*}

Hieu found a way to quickly calculate the value of $A_ N$ but he is unable to find a way to calculate $S_ N$. Your task is to help him to calculate this value.

Input

The input starts with the number of test cases $T$ followed by $T$ test cases ($T \leq 1\, 000$). Each test case consists of a positive integer $N$ ($1 \leq N \leq 10^{15}$).

Output

For each test case in the input, print in a single line the value $S_ N$ modulo $10^9+7$.

Sample Input 1 Sample Output 1
3
2
10
100
3
231
55041