题目背景

D(n)表示n的所有数位之和，有多少个n满足 10^L≤n≤10^R 并且 D(k*n) = k * D(n)?输出答案并将答案对10^9+7取模。

输入

第一行包含一个正整数t(1≤t≤10^4)——测试数据的个数；

每个测试数据包含三个整数 l, r, k(0≤l<r≤10^9, 1≤k≤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

对于上面这道题，下面是我的代码（暴力写法，可能不准确，大家帮我修改一下，让它运行得快一点），现在的问题主要是：我的答案不对

我的代码：

#include <bits/stdc++.h>

using namespace std;

long long cnt = 0;
const long long MOD = 1e9 + 7;

long long D(long long n) {
	long long sum = 0;
	string s = to_string(n);
	int len = s.size();
	for (long long i = 0; i < len; i++) {
		int num = s[i] - '0';
		sum += num;
	}
	return sum;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int l, r, k;
		scanf("%d%d%d", &l, &r, &k);
		int left = pow(10, l);
		int right = pow(10, r);
		for (long long i = left; i <= right; i++) {
			if (D(k * i) == k * D(i)) {
				cnt++;
			}
		}
		printf("%lld\n", cnt % MOD);
	}
	
	return 0;
}

请各位大佬帮忙Debug一下