# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# m-Beautiful Numbers

By moshiur_cse15 · Limits 3s, 512 MB

An m-Beautiful Number is a number which is divisible by `\$m\$` and the sum of the digits is also divisible by `\$m\$`. For example, `\$268\$` is a 4-Beautiful Number, but `\$68\$` and `\$26\$` are not 4-Beautiful Number.

In this problem, you'll be given `\$3\$` integers, `\$L\$`, `\$R\$`, and `\$m\$`, and you have to tell the number of m-Beautiful Numbers in between L and R (inclusive) . As the answer can be very large, you have to print it modulo `\$10^9 + 7\$`.

## Input

The first line of the input will contain a number `\$T\$` (`\$1 ≤ T ≤ 10^5\$`), number of test cases to follow. Next `\$T\$` lines will contain `\$3\$` integers `\$L\$`, `\$R\$` (`\$1 ≤ L ≤ R ≤ 10^{50}\$`), and `\$m\$` (`\$1 ≤ m ≤ 50\$`) each as stated in description.

## Output

For each case, you have to print the number of m-Beautiful Numbers in between `\$L\$` and `\$R\$` (inclusive) modulo `\$10^9 + 7\$`.

## Sample

InputOutput
```2
1 20 3
1 20 4```
```6
2
```

3-Beautiful Numbers between `\$1\$` to `\$20\$`: `\$3\$`, `\$6\$`, `\$9\$`, `\$12\$`, `\$15\$`, and `\$18\$`.

4-Beautiful Numbers between `\$1\$` to `\$20\$`: `\$4\$`, and `\$8\$`.

### Statistics

39% Solution Ratio

dip_BRUREarliest, Dec '19

EgorKulikovFastest, 0.9s

dip_BRURLightest, 18 MB

steinumShortest, 1086B