Problem F
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 |
