| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 256 MB | 3 | 1 | 1 | 100.000% |
Alice, Bob and Eve are playing a game on craft papers. Every time Eve tells a natural number, Alice and Bob can write the number (in the decimal representation) on their own papers, add a plus sign or a minus sign before each digit, and then evaluate the arithmetic expression he or she has wrote. The one with the lower absolute value wins. If their absolute values are the same, it will cause a draw and they will play one more time.
Actually, if they are smart, the game will never end. So after a while, they turn to focus on the optimal solution of the puzzle game. Let $f(m)$ be the minimal absolute value that can be built from $m$. They are wondering if you can help them determine $f(m)$ for $l \leq m \leq r$.
However, after realizing your perfect programming skill, they decided to make a puzzle for you as well. They have set several questions $(l, r)$ for you, and your task is to find the sum of all the integers $m$ between $l$ and $r$ (inclusive) satisfying $f(m) = k$ for $k = 0, 1, 2, \ldots, 9$ and report the answer modulo $(10^9 + 7)$.
The first line contains one integer $n$ (1ドル \leq n \leq 5000$) indicating the number of questions.
Each of the next $n$ lines contains two integers $l$ and $r$ (1ドル \leq l \leq r \leq 10^{100}$) indicating a question.
For each question, output ten space-separated integers in one line, where the $i$-th integer indicates the sum of all the integers $m,ドル satisfying that $l \leq m \leq r$ and $f(m) = i,ドル modulo $(10^9 + 7)$.
7 1 10 11 50 51 100 101 500 501 1000 19260817 19260818 1234567890123456789 1234567890987654321
0 11 2 3 4 5 6 7 8 9 110 210 211 193 166 180 84 47 19 0 385 770 579 497 424 310 306 243 171 90 19080 34666 27312 19047 10615 5490 2594 1097 299 0 43695 81005 67134 55962 46289 35085 23872 13924 6385 1899 19260817 19260818 0 0 0 0 0 0 0 0 230833519 749351908 0 0 0 0 0 0 0 0
The digits of 19260817ドル$ in the decimal representation are $\{1, 9, 2, 6, 0, 8, 1, 7\},ドル which can build an arithmetic expression $(+1-9-2-6+0+8+1+7),ドル whose value and abosolute value are 0ドル$.
The digits of 19260818ドル$ in the decimal representation are $\{1, 9, 2, 6, 0, 8, 1, 8\},ドル which can build an arithmetic expression $(+1-9+2+6-0-8-1+8),ドル whose value is $-1$ and aboslute value is 1ドル$.