Reykjavík Random 17

Start

2022-01-06 10:00 AKST

Reykjavík Random 17

End

2022-01-13 10:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -139 days 12:03:47

Time elapsed

168:00:00

Time remaining

0:00:00

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