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$


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$).


For each test case, print the result modulo $10^9+7$ in a single line.

Sample Input 1 Sample Output 1
1 9 2 0
1 9 2 1
1 99 2 1
CPU Time limit 2 seconds
Memory limit 256 MB
Source The 2017 ACM - ICPC Vietnam National Programming Contest
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in