← 返回题目列表

Codeforces · 1985/G

G. D 功能

中文机器翻译题面 查看原题

设 $$$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$$$)。

输出

对于每个测试用例,输出一个整数,即答案,模 $$$10^9 + 7$$$。

示例

输入 #1

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

输出 #1

2
3
90
12
974995667
999

注意

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

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

对于第三个测试用例,$$$n$$$ 之间的所有值(包括 $$$10$$$ 和 $$$100$$$ 除外)都满足条件。