8629: Sumire
内存限制：128 MB
时间限制：3 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
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).
where f(x,B,d) means the number of times that digit d appears in the ba
输入格式
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, 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