1985G.md (1088B)
1 Source: https://codeforces.com/problemset/problem/1985/G 2 3 G. D-Function 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let $D(n)$ represent the sum of digits of $n$. For how many integers $n$ where $10^{l} \leq n \lt 10^{r}$ satisfy $D(k \cdot n) = k \cdot D(n)$? Output the answer modulo $10^9+7$. 22 23 Input 24 25 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) – the number of test cases. 26 27 Each test case contains three integers $l$, $r$, and $k$ ($0 \leq l \lt r \leq 10^9$, $1 \leq k \leq 10^9$). 28 29 Output 30 31 For each test case, output an integer, the answer, modulo $10^9 + 7$. 32 33 Example 34 35 Input 36 37 ``` 38 6 39 40 0 1 4 41 42 0 2 7 43 44 1 2 1 45 46 1 2 3 47 48 582 74663 3 49 50 0 3 1 51 ``` 52 53 Output 54 55 ``` 56 2 57 3 58 90 59 12 60 974995667 61 999 62 ``` 63 64 Note 65 66 For the first test case, the only values of $n$ that satisfy the condition are $1$ and $2$. 67 68 For the second test case, the only values of $n$ that satisfy the condition are $1$, $10$, and $11$. 69 70 For the third test case, all values of $n$ between $10$ inclusive and $100$ exclusive satisfy the condition.