Encoding

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/AUG19/hindi/ENCODING.pdf), [Bengali](http://www.codechef.com/download/translated/AUG19/bengali/ENCODING.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/AUG19/mandarin/ENCODING.pdf), [Russian](http://www.codechef.com/download/translated/AUG19/russian/ENCODING.pdf), and [Vietnamese](http://www.codechef.com/download/translated/AUG19/vietnamese/ENCODING.pdf) as well. Chef is trying to open the oven in his kitchen to cook some cookies. However, the oven is special ― you need a password to open it. Let's define a function $f(x)$ for a positive integer $x$ as follows:  Consider the decimal representation of $x$ (without leading zeros). Split it into the minimum number of contiguous subsequences of digits such that in each subsequence, all digits are identical.  For each subsequence, look at its position in the original decimal representation of $x$. Let's say that the most significant digit it contained was the $e$th digit, where $e=0$ corresponds to the least significant digit of $x$. For example, $388,822,442$ can be split into subsequences "3", "888", "22", "44", "2", where $e=7$ for the sequence "888" and $e=4$ for the sequence "22".  The *value* of a subsequence which contains a digit $d$ repeated one or more times is $d \cdot 10^e$.  $f(x)$ is the sum of values of these subsequences. For example, $f(388,822,442) = 3 \cdot 10^8 + 8 \cdot 10^7 + 2 \cdot 10^4 + 4 \cdot 10^2 + 2 \cdot 10^0$. The oven has a screen which displays two long integers $L$ and $R$ (with $N_L$ and $N_R$ digits respectively, without leading zeros). The password is the sum of $f(x)$ for each $x$ between $L$ and $R$ inclusive. Chef does not have a lot of time, so he asks for your help. Please find the password for the oven so that he can start cooking as fast as possible. Since this number could be very large, compute it modulo $10^9 + 7$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N_L$ and $L$.  The second line contains two spaceseparated integers $N_R$ and $R$. ### Output For each test case, print a single line containing one integer ― the password. ### Constraints  $1 \le T \le 10$  $1 \le N_L, N_R \le 10^5$  $1 \le L \le R \lt 10^{100,000}$  $L$ and $R$ do not contain leading zeros ### Subtasks **Subtask #1 (10 points):**  $R  L \le 10^5$  $R \lt 10^{18}$ **Subtask #2 (20 points):** $R \lt 10^{18}$ **Subtask #3 (70 points):** original constraints ### Example Input ``` 3 1 9 2 97 1 8 2 12 1 1 1 8 ``` ### Example Output ``` 4681 49 36 ``` ### Explanation **Example case 2:** $f(8) = 8, f(9) = 9, f(10) = 10, f(11) = 10, f(12) = 12$Author:  claudy 
Editorial  https://discuss.codechef.com/problems/ENCODING 
Tags  aug19, claudy, claudy, digitdp, dynamicprogramming, easymed, vijju123 
Date Added:  28042019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 