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.

3
1 9 2 0
1 9 2 1
1 99 2 1

36
0
1503