Problem F
Familiar Digit
A digit is called familiar to an array of positive integers if that digit appears in every elements of the array. For example, an array $[14, 1470, 161240, 111000444]$ has $2$ familiar digits: $1$ and $4$. Also note that, $0$ is not a familiar digit because $0$ doesn’t appear in the first element $14$ (we don’t count leading zeros).
Given $A$, $B$, $k$ and $d$, your task is to count the number of increasing arrays $X=[X_1,X_2,\ldots ,X_ K]$ of length $K$ that has exactly $d$ familiar digits where: $A \leq X_1<X_2<\ldots <X_ K \leq B$
Input
The input starts with the number of test cases $T$ ($T \le 100$). Then $T$ test cases follow, each is printed in a line and consists of $4$ numbers $A$, $B$, $K$ and $d$ ($1 \leq A \leq B < 10^{18}$, $2 \leq K \leq 10$, $0 \leq d \leq 10$).
Output
For each test case, print the result modulo $10^9+7$ in a single line.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 9 2 0 1 9 2 1 1 99 2 1 |
36 0 1503 |
