7214：Sumire

题目描述

Calculate

$$
\sum_{i=l}^r f^k(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 $0^0=0$.

输入解释

The first line contains one integer $T$ ($1\le T\le 10^4)$, denoting the number of test cases.

For each test case, the only line contains five integers $k,B,d,l,r$ ($0\le k\le 10^9$, $2\le B\le 10^9$, $0\le d< B$, $1\le l\le r\le 10^{18})$, as the statement shows.

输出解释

For each test case, output an integer indicating the answer modulo $10^9+7$ in a single line.

输入样例

3
2 2 0 1 5
1 4 3 11 45
10 14 11 19 198

输出样例

6
19
1049

来自杭电HDUOJ的附加信息

Hint

For the first case in the sample, the answer is$$\begin{aligned}&\sum_{i=1}^5 f^2(i,2,0)\\\\&=0^2+1^2+0^2+2^2+1^2\nonumber\\\\&=6\nonumber\end{aligned}$$

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2022“杭电杯”中国大学生算法设计超级联赛（7）

源链接： HDU-7214

最后修改于 2022-09-15T06:17:26+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
7000/3500MS(Java/Others)	524288/524288K(Java/Others)