6602: Sumire
内存限制：128 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Calculate
where f(x,B,d) means the number of times that digit d appears in the base-B form of x (ignoring leading zeros).
In this problem, we consider that 00=0.
∑i=lrfk(i,B,d)
where f(x,B,d) means the number of times that digit d appears in the base-B form of x (ignoring leading zeros).
In this problem, we consider that 00=0.
输入
The first line contains one integer T (1≤T≤104), denoting the number of test cases.
For each test case, the only line contains five integers k,B,d,l,r (0≤k≤109, 2≤B≤109, 0≤d<B, 1≤l≤r≤1018), as the statement shows.
For each test case, the only line contains five integers k,B,d,l,r (0≤k≤109, 2≤B≤109, 0≤d<B, 1≤l≤r≤1018), as the statement shows.
输出
For each test case, output an integer indicating the answer modulo 109+7 in a single line.
样例输入 复制
3
2 2 0 1 5
1 4 3 11 45
10 14 11 19 198样例输出 复制
6
19
1049