 2017 Asia HCMC Vietnam National Programming Contest #### Start

2017-11-04 17:00 AKDT

## 2017 Asia HCMC Vietnam National Programming Contest

#### End

2017-11-04 22:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1413 days 15:11:25

5:00:00

0:00:00

# Problem FFamiliar 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