题目描述

设 $D(n)$ 表示 $n$ 的各位数字之和。有多少个整数 $n$ 满足 $10^{l} \leq n < 10^{r}$，且 $D(k \cdot n) = k \cdot D(n)$？请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例包含三个整数 $l$、$r$ 和 $k$（$0 \leq l < r \leq 10^9$，$1 \leq k \leq 10^9$）。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的 $n$ 的个数，对 $10^9+7$ 取模。

样例

6
0 1 4
0 2 7
1 2 1
1 2 3
582 74663 3
0 3 1

2
3
90
12
974995667
999

样例说明

对于第一个测试用例，唯一满足条件的 $n$ 是 $1$ 和 $2$。

对于第二个测试用例，唯一满足条件的 $n$ 是 $1$、$10$ 和 $11$。

对于第三个测试用例，所有 $n$ 满足 $10 \leq n < 100$ 的值都满足条件。

由 ChatGPT 4.1 翻译

来源

Codeforces 1985G，英文题名 D-Function。